Top-Down Lower Bounds for Depth-Four Circuits
summary
New top-down proof shows parity needs size exp(Θ(n^{1/3})) for depth‑4 circuits by combining two concrete tools: a block unpredictability lemma that picks random blocks of size ≈n^{1/3} and proves their bits remain fully unconstrained given few outside coordinates, and a robust sunflowers construction that converts dense Hamming‑ball neighborhoods into mirror sets. The argument picks a large subcircuit, finds a mirror set of yes‑inputs, flips whole blocks to create local limits, and forces a CNF to accept a wrong parity input, giving the exponential lower bound.
AI-written summary · about
chapters (11)
- 0:00Introduction to circuits
- 1:05Parity function complexity
- 2:35Depth-two lower bounds
- 6:18Depth-three circuit analysis
- 9:40Classical lower bound methods
- 13:56Research motivation and history
- 17:39Main results and goals
- 22:19The unpredictability lemma
- 34:28Proving depth-three bounds
- 40:45Depth-four challenges
- 51:08Conclusion and future outlook
related talks
16mOn Oracles and Algorithmic Methods for Proving Lower Bounds
22mNew Lower Bounds and Derandomization for ACC, and a...
32mA Finite Alternation Result for Reversible Boolean Circuits
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
19mAlgorithms and Lower Bounds for Comparator Circuits from Shrinkage
51mOn constant T-depth circuits
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders