Top-Down Lower Bounds for Depth-Four Circuits
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a comprehensive lecture on top-down lower-bound methods for depth-4 boolean circuits. Delve into a new proof demonstrating that the parity function requires depth-4 circuits of size exponential in n^1/3. Examine the application of robust sunflowers and block unpredictability in this proof. Learn from Mika Göös of EPFL as he presents this structural result, co-authored with Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov. Gain insights into advanced topics in circuit complexity theory during this hour-long presentation from the Simons Institute.
Syllabus
Top-Down Lower Bounds for Depth-Four Circuits
Taught by
Simons Institute
Related Courses
Computational Complexity TheoryIndian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam Proof and Circuit Complexity - Robert Robere
Institute for Advanced Study via YouTube Quantum Complexity - Quantum Computation at CMU
Ryan O'Donnell via YouTube Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube