Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers - Toniann Pitassi
Offered By: Institute for Advanced Study via YouTube
Course Description
Overview
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.
Syllabus
Intro
Boolean circuits
Formulas
Milestones
Sunflower lemma
Spread lemma
Spread lemma proof
Block respecting sets
Approximating sets
Decomposition
Lifting Theorem
Taught by
Institute for Advanced Study
Related Courses
Algebra & AlgorithmsMoscow Institute of Physics and Technology via Coursera Proof and Circuit Complexity - Robert Robere
Institute for Advanced Study via YouTube Undergrad Complexity at CMU - SAT
Ryan O'Donnell via YouTube Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures
Association for Computing Machinery (ACM) via YouTube Wolverine - Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits
IEEE via YouTube