New Lower Bounds and Derandomization for ACC, and a...
summary
Proves concrete derandomization and lower-bound steps: shows MA_sub_ACC0 ⊆ i.o.NQP with quasi‑polynomial verification but polynomial‑length proofs, uses PCPs plus a construction of a PSPACE‑complete language admitting an AC0^2 instance checker, and replaces a TC0 bottleneck by polynomial interpolation over F2. Combining padding and diagonalization yields a sub‑half‑exponential lower bound against ACC0 (NEXP not in circuits of size g(g(n)) for subexp g) and strong average‑case resistance (no 1/2+1/poly approximation) for NQP subclasses.
AI-written summary · about
chapters (8)
- 0:00Background
- 7:13Lower Bounds
- 13:45What can go wrong
- 20:25Previous work
- 24:30Generalization perspective
- 27:50Diagonalization
- 32:20Proof
- 40:30Review
related talks
22mNew Lower Bounds and Derandomization for ACC, and a...
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
57mTowards P≠NP from Extended Frege Lower Bounds
47mNatural Proofs in Algebraic Circuit Complexity
55mLower Bounds Against PC With Extension Variables
01h 31mTutorial 1: The GCT Chasm I
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
21mBlack-box Constructive Proofs are Unavoidable