International School-conference in Algorithms, Combinatorics, and Complexity

24 May 2021, 10:00 → 28 May 2021, 21:00 Europe/Moscow

Zoom

School in Algorithms, Combinatorics, and Complexity

May 24 - May 28, 2021

An advanced school for young researchers featuring three minicourses in vibrant areas of mathematics and computer science.  The target audience includes graduate, master, and senior bachelor students of any mathematical speciality.

---

Lecturers:

Maria Chudnovsky	Fedor Fomin	Madhu Sudan
Princeton University	University of Bergen	Harvard University

 

Courses

---

Forbidding Induced Subgraphs (Maria Chudnovsky)

The study of the structure of graphs with certain induced subgraphs forbidden has been an active area of research in graph theory in recent years, after the long standing Strong Perfect Graph Conjecture was proved using structural methods. The goal of this course is to cover some of the recent developments in the area. We will start with simple theorems about forbidden induced subgraphs, and work our way up to the latest research results. The topics will include perfect graphs, claw-free graphs, coloring graphs with forbidden induced subgraphs, algorithms for detecting induced subgraphs and others.

---

Representative Families and Algorithms (Fedor Fomin)

The theorems of Bollobás (1965) and Lovász (1977) about set pairs are fundamental results in extremal set theory. In this tutorial, we discuss some algorithmic applications of these classical theorems. In particular, we learn about representative families and their role in kernelization,  enumeration, and parameterized algorithms.

---

Highlights of Algorithmic Coding Theory (Madhu Sudan)

In this series of talks, we will quickly introduce the mathematical notions of an error-correcting code, and the associated notions of Encoding and Decoding Algorithms. After reviewing some of the classical results on the existence, construction and limits on error-correcting codes, we will zoom in on two results in the field.

1. The construction of capacity achieving codes (based on Folded Reed Solomon Codes) over large alphabets and their encoding and decoding: Given any error parameter $\delta \in [0, 1]$ and $\varepsilon > 0$, these codes achieve a rate $1 - \delta - \varepsilon$ and correct $\delta$ fraction of adversarial errors with alphabet size growing only with $\varepsilon$.
2. The construction of binary error correcting codes (Polar codes) that achieve Shannon capacity at small block lengths: I.e, given $\delta \in [0, 1 / 2]$ and $\varepsilon > 0$ correct delta fraction of random errors with rate $1 - \mathrm{h}(\delta) - \varepsilon$ at lengths $\mathrm{poly}(1 / \varepsilon)$. [Here $\mathrm{h}(p) = -p \log_2 p - (1 - p) \log_2 (1-p)$ is the binary entropy function].

Both results come with polynomial time algorithms!

Videos

Youtube channel

---

Local Organizers:

• Dmitry Sokolov

---

Institutions participating in the organization of the event:

• Department of Mathematics and Computer Science of St Petersburg University
• Leonhard Euler International Mathematical Institute in Saint Petersburg

The school is supported by a grant from the Government of the Russian Federation, agreements 075-15-2019-1619 and 075-15-2019-1620.

Representative Families and Algorithms

• Representative Families and Algorithms-1.pdf
• Representative Families and Algorithms-2.pdf
• Representative Families and Algorithms-3.pdf

Thursday Talks

• A Few Words About the Proof Complexity.pdf
• Data Structures Meets Circuits and Cryptography.pdf
• Karchmer--Raz--Wigderson Conjecture.pdf
• Thursday talks.pdf

Monday, 24 May

16:50 → 17:00 Connection to the school’s zoom and a greeting word from organizers

17:00 → 18:00 Forbidding Induced Subgraphs (Lecture 1)

Speaker: Prof. Maria Chudnovsky (Princeton University)

18:15 → 19:15 Representative Families and Algorithms (Lecture 1)

Speaker: Prof. Fedor Fomin (University of Bergen)

19:30 → 20:30 Highlights of Algorithmic Coding Theory (Lecture 1)

Speaker: Prof. Madhu Sudan (Harvard University)

Tuesday, 25 May

17:00 → 18:00 Representative Families and Algorithms (Lecture 2)

Speaker: Prof. Fedor Fomin (University of Bergen)

18:15 → 19:15 Highlights of Algorithmic Coding Theory (Lecture 2)

Speaker: Prof. Madhu Sudan (Harvard University)

19:30 → 20:30 Forbidding Induced Subgraphs (Lecture 2)

Speaker: Prof. Maria Chudnovsky (Princeton University)

Wednesday, 26 May

17:00 → 18:00 Highlights of Algorithmic Coding Theory (Lecture 3)

Speaker: Prof. Madhu Sudan (Harvard University)

18:15 → 19:15 Forbidding Induced Subgraphs (Lecture 3)

Speaker: Prof. Maria Chudnovsky (Princeton University)

19:30 → 20:30 Representative Families and Algorithms (Lecture 3)

Speaker: Prof. Fedor Fomin (University of Bergen)

Thursday, 27 May

17:00 → 17:45 A Few Words About the Proof Complexity

Speaker: Dr Dmitry Sokolov (St. Petersburg State University)

17:55 → 18:40 Karchmer--Raz--Wigderson Conjecture

Speaker: Dr Ivan Mihajlin (The Euler International Mathematical Institute)

18:50 → 19:35 Data Structures Meet Circuits and Cryptography

Speaker: Dr Alexander Golovnev (Georgetown University)

Friday, 28 May

17:00 → 18:00 Forbidding Induced Subgraphs (Lecture 4)

Speaker: Prof. Maria Chudnovsky (Princeton University)

18:15 → 19:15 Representative Families and Algorithms (Lecture 4)

Speaker: Prof. Fedor Fomin (University of Bergen)

19:30 → 20:30 Highlights of Algorithmic Coding Theory (Lecture 4)

Speaker: Prof. Madhu Sudan (Harvard University)