Top-Down Lower Bounds for Bounded Depth Circuits - Oliver Korten @videosfromIAS
Top-Down Lower Bounds for Bounded Depth Circuits - Oliver Korten  @videosfromIAS
Uploaded October 2026 | Updated November 2026, 12 hours ago
Computer Science/Discrete Mathematics Seminar II
10:30am|Simonyi Hall 101 and Remote Access
Topic: Top-Down Lower Bounds for Bounded Depth Circuits
Speaker: Oliver Korten
Affiliation: Institute for Advanced Study
Date: October 13, 2026

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?
Top-Down Lower Bounds for Bounded Depth Circuits - Oliver KortenA Review of the BFSS Conjecture - Part 3 - Aidan HerderscheeAubry-Mather Theory, Complete Devil Stair Case and Fractional Quantum Hall Effects - Jinxin XueThe Nearby Lagrangian Conjecture: A Start - Bingyu ZhangDynamical Aspects of Sofic and Non-Sofic Groups - Benjy WeissLove Numbers and Waveform Resummation from Black Hole Scattering Amplitudes - Mikhail IvanovLagrangian Cobordisms and Persistence Modules - Leonid PolterovichPutting Contact Geometry in Order: Orderability and Contact Rigidity - Jakob HedickeAlgebraic Hodge Generic Points are Dense - Gregorio BaldiSystolic Geometry and Viterbo’s Conjecture Under Finite Symmetry - Shira TannyCritical Intent as a Form of Life - April 19 PhotosThe astrophysics of binary black holes after a decade of gravitational-wave.... - Sylvia Biscoveanu
Institute for Advanced Study |

Top-Down Lower Bounds for Bounded Depth Circuits - Oliver Korten

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER