Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers - Toniann Pitassi

Explore the intricate world of computational complexity theory in this Members' Seminar talk delivered by Toniann Pitassi from the University of Toronto. Delve into the fascinating connections between lower bounds in complexity theory, communication complexity, and sunflowers. Gain insights into Boolean circuits, formulas, and key milestones in the field. Examine the sunflower lemma, spread lemma, and its proof, along with concepts such as block respecting sets and approximating sets. Investigate the decomposition process and the Lifting Theorem. Enhance your understanding of advanced topics in theoretical computer science and mathematics through this comprehensive lecture.

Intro
Boolean circuits
Formulas
Milestones
Sunflower lemma
Spread lemma
Spread lemma proof
Block respecting sets
Approximating sets
Decomposition
Lifting Theorem