Главная
Study mode:
on
1
Intro
2
Boolean circuits
3
Formulas
4
Milestones
5
Sunflower lemma
6
Spread lemma
7
Spread lemma proof
8
Block respecting sets
9
Approximating sets
10
Decomposition
11
Lifting Theorem
Description:
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.

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

Institute for Advanced Study
Add to list
0:00 / 0:00