Journey with Eric Allender: From Turing Machines to Circuits, and Back
summary
Tracks historical reductions and concrete proofs: shows Valiant‑Vazirani isolation turning NP instances into ones with a single accepting path, recalls Immerman–Szelepcsényi NL=coNL inductive counting, and highlights concrete circuit vs. machine transformations (Pippenger–Fischer tableau yields size ~t·log t circuits, unbounded fan‑in trades depth for t/log log t). Records Allender’s uniform lower bound that permanent avoids subexponential ACC0, uniform division in TC0, and that barely superlinear lower bounds would already separate major classes.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:00Turing Machines
- 3:40Transformation
- 4:10Timebound Rate
- 5:25Efficiency Reduction
- 8:30Alternating Computation
- 10:00Circuits
- 18:50Graph Connect Activity
- 20:15Small Lab Circuits
- 21:00Proof
- 23:00Basic functions
- 23:55Division
- 27:50Piping Giant Fish
- 29:20Can you do better
- 30:30Sorting
related talks
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
47mNatural Proofs in Algebraic Circuit Complexity
22mNew Lower Bounds and Derandomization for ACC, and a...
01h 01mThe Gospel According to TCS
01h 22mTutorial 5: The GCT Chasm II
21mBlack-box Constructive Proofs are Unavoidable
44mTuring's Toy - The story of a mathematical idea that changed the world
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic