
Top-Down Lower Bounds for Bounded Depth Circuits
Oliver Korten, speaking at the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar, presents a new proof that constant-depth circuits with unbounded fan-in AND/OR gates need exponential size to compute the parity function. Two proofs of this result exist from the 1980s, one built on random restrictions and one on approximation by low-degree polynomials. Korten tackles a third approach, proposed by Hastad, Jukna, and Pudlak, that frames the lower bound in the language of communication complexity and argues from the top of the circuit downward, a direction motivated by Karchmer and Wigderson's long-standing program for depth lower bounds. The talk centers on a combinatorial question: how closely a high-entropy random variable restricted to a small random subset of coordinates resembles the uniform distribution. The seminar runs just over two hours and assumes familiarity with circuit complexity and communication complexity.