Proof of NEXP Not in ACC
summary
Proves that showing a faster ACC-SAT algorithm yields circuit lower bounds: a subexponential-time SAT routine for constant-depth mod-m circuits implies some X^NP language needs 2^{N^ε}-size ACC and yields a NEXP language with no quasi‑polynomial ACC families. Key steps: reduce any NEXP instance to succinct 3-SAT (NEXP-complete), assume small ACC witness circuits exist, nondeterministically guess a small circuit encoding a satisfying assignment and verify it using the SAT routine, and run the verification by rewriting ACC gates via the G of Hs decomposition and fast multilinear evaluation.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:13Defining ACC circuits
- 1:02Circuit complexity background
- 17:05Proof strategy overview
- 19:00Succinct 3SAT problem
- 22:58Reductions to 3SAT
- 27:32Strong reduction lemma
- 30:23Contradiction argument
- 36:02Easy witness argument
- 38:53Fast SAT algorithm design
- 45:00Constructing the checker D
- 52:14Recap of SAT algorithm
- 56:45Hardness-randomness techniques
- 1:02:34PCP and open problems
related talks
29mImproved Deterministic Algorithms for Sparse Max-SAT
17mSatisfiability Algorithms Based on Concentrated Shrinkage
01h 21mComputational Complexity in Theory and in Practice
31mFaster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p]
35mWhy Extension-Based Proofs Fail
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
31mParameterized Verification of Systems with Precise (0,1)-Counter Abstraction
25mLower Bounds for Problems Parameterized by Clique-width