Computer Science/Discrete Mathematics Seminar II
Top-Down Lower Bounds for Bounded Depth Circuits
A cornerstone result in complexity theory is that O(1)-depth circuits with unbounded fan-in AND/OR gates computing the parity of an n bit string must have exp(n) size. Two completely different proofs of this are known, both dating back to the 1980's; the first is based on the method of random restrictions, and the second on approximation by low-degree polynomials. Motivated by Karchmer and Wigderson's communication complexity program for proving lower bounds against super-logarithmic depth circuits (a central problem which remains wide open), Hastad, Jukna, and Pudlak set out in search of a THIRD proof of the lower bound for parity, one which can be framed in the language of communication complexity and which reasons from the top of the circuit downwards. We present the first such proof. The underlying combinatorics center around the following problem: if X is a high entropy random variable in {0,1}^n, and R is a random small subset of [n], in what sense will X_R typically resemble the uniform distribution?