New Lower Bounds and Derandomization for ACC, and a...
summary
Proves concrete circuit lower bounds and derandomizations: shows MA_sub_ACC0 has no n^k-size ACC0 circuits by building an AC0-parity verifier from a PSPACE-complete, AC0-instance-checkable language, then derandomizes that subclass into NQP via a derandomization-centric algorithmic method, resolving the “infinitely-often” mismatch so hardness transfers. Delivers alternative proofs of Williams’s results and new bounds that NEXP has no sub-third- and sub-half-exponential-size ACC0 circuits, plus quasi-polynomial-time derandomization with polynomial nondeterminism.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:15Today's Plan
- 0:42(Oversimplified) History and Motivation
- 5:19Williams' Original Proof: Proof by Contradiction
- 6:27A Derandomization-centric Perspective
- 7:15A Lower Bound for a subclass of MA against
- 11:58The infinitely often issue
- 12:59New Results via this New Perspective
- 15:27Proof Overview
- 17:17Technical Ingredient
related talks
53mNew Lower Bounds and Derandomization for ACC, and a...
47mRange Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
01h 01mTop-Down Lower Bounds for Depth-Four Circuits
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
01h 31mTutorial 1: The GCT Chasm I
55mNon-commutative Computation
51mAllender's Conjecture and its Impacts on Meta-Complexity
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits