Top-Down Lower Bounds for Depth-Four Circuits

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=DdeOJaWF4jo


Duration: 1:00:30
314 views
8

Mika Göös (EPFL)
https://simons.berkeley.edu/talks/mika-goos-epfl-2023-07-24
Structural Results

We present a top-down lower-bound method for depth-4 boolean circuits. In particular, we give
a new proof of the well-known result that the parity function requires depth-4 circuits of size
exponential in n^1/3. Our proof is an application of robust sunflowers and block unpredictability.
Coauthors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov



Other Videos By Simons Institute for the Theory of Computing


2023-07-28Randomized versus Deterministic Decision Tree Size
2023-07-28Fourier Growth of XOR-Fibers of Communication Protocols
2023-07-27Sign-rank vs Margin
2023-07-27Tight Space Complexity of the Coin Problem
2023-07-27A New Upper Bound for the Heilbronn Triangle Problem
2023-07-26A Polynomial Bogolyubov type Result for the Special Linear Group
2023-07-26Higher-dimensional Expansion of Random Geometric Complexes
2023-07-26Testing Thresholds for High-dimensional Sparse Random Geometric Graphs
2023-07-25An Improved Bound for Regular Partitions of Hypergraph of Bounded VC_2 Dimension
2023-07-25Larger Corner-free Sets in High Dimensions
2023-07-25Top-Down Lower Bounds for Depth-Four Circuits
2023-07-25P-smallness of Increasing Families
2023-07-24Nearly all k-SAT Functions are Unate
2023-07-21Session #3
2023-07-20Survey on Optimization in FL
2023-07-20Session #2
2023-07-20Survey on Privacy/Security in FL
2023-07-20Session #1
2023-07-19Keynote
2023-07-19Another Round Of Breaking and Making Quantum Money: How to Not Build It From Lattices and More
2023-07-19Applications of Bit Commitments in a Quantum World


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Structural Results
Mika Göös