Circuit Depth Reductions
summary
Proves structural depth reductions: any size-S circuit is an OR of 2^{S/3} formulas (toy lemma) and the main result gives a depth-3 with top fan-in 2^{S/3.9} whose bottom gates are linear-size CNFs, so improving pseudorandom constructions against these classes yields superlinear circuit lower bounds. For De Morgan formulas a conjectured probabilistic polynomial of degree sqrt(S) lets a size ~n^4 formula be written as a subexponential sum of F2 polynomials of sublinear degree, using approximate/robust polynomials, Chernoff and Fourier expansions.
AI-written summary · about