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 & Algorithms
Moscow 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