An Overview of Quantified Derandomization

on YouTube ↗37m

" summary

Quantified derandomization asks: given a circuit, decide whether it accepts all but B inputs or rejects all but B inputs. Unconditional algorithms exist for AC0 depth D when B = 2^n / polylog(n) with polylog power ≈ D−2, using restriction/switching lemmas plus explicit extractors, and run in n^{log^2 n} time. Those parameters are provably tight for black‑box reductions, so progress needs white‑box samplers or nondeterministic proofs. Separate frontiers: sparse LTF/TC0 bounds via similar methods, and constructing small hitting sets for polynomials over large fields.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 1:10Survey talk
3. 7:59Active research directions
4. 11:31TCO, LTF and PTF circuits
5. 15:52Algorithmic restrictions
6. 17:23Reduction from standard derand 3 error reduction using an extractor / sampler
7. 18:22Explicit extractors in weak models
8. 19:41Limitation of blackbox techniques
9. 21:40Whitebox techniques already available
10. 23:50Reduction from standard derand 3 error reduction using an extractor/sampler
11. 30:04Approach for TC lower bounds
12. 31:48Interesting directions in quant derand