Concrete Computational Complexity Measures
Event details
| Date | 11.07.2023 |
| Hour | 16:00 › 18:00 |
| Speaker | Artur Riazanov |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Co-examiner: Prof. Michael Kapralov
Abstract
A sunflower with p petals consists of p sets whose pairwise intersections are identical. Erdos and Rado proved that every family of k-element sets of size at least k! (p - 1)^k contains a sunflower of size p. In this write-up we discuss the recent improvement of the Erdos-Rado sunflower lemma [Rao19] and two [CKR20,LMMPZ22] of its many applications to theoretical computer science.
Background papers
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Co-examiner: Prof. Michael Kapralov
Abstract
A sunflower with p petals consists of p sets whose pairwise intersections are identical. Erdos and Rado proved that every family of k-element sets of size at least k! (p - 1)^k contains a sunflower of size p. In this write-up we discuss the recent improvement of the Erdos-Rado sunflower lemma [Rao19] and two [CKR20,LMMPZ22] of its many applications to theoretical computer science.
Background papers
- Lifting with Sunflowers https://www.cs.toronto.edu/~mertz/papers/lmmpz20.lifting_with_sunflowers.pdf [excluding section 7]
- Coding for Sunflowers https://arxiv.org/pdf/1909.04774.pdf [sections 1-3]
- Monotone Circuit Lower Bounds from Robust Sunflowers https://arxiv.org/pdf/2012.03883.pdf
Practical information
- General public
- Free