LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Top-Down Lower Bounds for Bounded Depth Circuits
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Top-Down Lower Bounds for Bounded Depth Circuits

133 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime2 h 13 m
Compared with MathematicsLonger than 99%
Source channelInstitute for Advanced Study (YouTube)