Lower Bounds for NW-generators in AC0-Frege

on YouTube ↗33m

" summary

Proves a concrete conditional lower bound: for any symmetric f in NP ∩ CoNP that is exponentially hard for depth‑two AC0 circuits, the Nisan–Wigderson map NW_f,A (with a design matrix A) yields hard instances for AC0-Frege — τ_b(NW_f,A) for a random matrix A and random b is with probability 1−o(1) a tautology requiring superpolynomial (often exponential) AC0‑Frege proofs. Argument uses bounded arithmetic and nonstandard models, sigma1 encodings of f, combinatorial design matrices and pigeonhole-style combinatorics; it produces explicit lower‑bound families and two formalized corollaries.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to lower bounds
2. 1:02Candidates for hard formulas
3. 3:08Proof complexity generators
4. 5:13Origins and motivations
5. 7:33Nissan-Wigderson generators
6. 9:31Evidence for the conjecture
7. 13:44Representation and parity
8. 17:27AC0 complexity results
9. 20:24Soundness and completeness
10. 24:08Proof frameworks and apps
11. 29:45Open problems and closing