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.
Top-Down Lower Bounds for Depth-Four Circuits
Overview
Syllabus
Top-Down Lower Bounds for Depth-Four Circuits
Taught by
Simons Institute
Related Courses
-
Recent Structure Lemmas for Depth-Two Threshold Circuits
-
Lower Bounds for Tractable Arithmetic Circuits
-
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
-
Circuits - Graduate Complexity Lecture 4 at CMU
-
Circuit Lower Bounds from Algorithm Design - An Overview I
-
Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers - Toniann Pitassi
