Black-box Constructive Proofs are Unavoidable
summary
Main claim: proving NEXP not in a typical circuit class C is equivalent to the existence of a black-box constructivity — a randomized poly(n)-time oracle tester that distinguishes promised yes/no truth tables useful against C. Proof builds a special PCP system (smooth, strong, locally-decodable) that preserves witness lower bounds and lets Williams’ constructive-property reduction be bootstrapped from poly(2^n) to poly(n). Additional specifics: randomness is essential (deterministic polylog-time testers provably do not exist) and several bootstrapping and largeness variants are established.
AI-written summary · about
chapters (12)
- 0:00Start
- 0:13Overview
- 0:50How do we prove circuit lower bounds?
- 2:41Natural proofs
- 6:23How to overcome this "natural proof" barrier
- 7:52Stronger notions of constructivity?
- 8:06Black-box constructivity
- 8:55Some technical details
- 11:01Why BB constructivity seems much stronger
- 12:28Main theorem
- 13:48Proof ideas
- 19:54Open problems
related talks
51mAllender's Conjecture and its Impacts on Meta-Complexity
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
53mNew Lower Bounds and Derandomization for ACC, and a...
23mSmooth, Integrated Proofs of Cryptographic Constant Time for Nondeterministic Programs(…)
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
01h 01mTop-Down Lower Bounds for Depth-Four Circuits
01h 31mTutorial 1: The GCT Chasm I
19mSimplifying Safety Proofs with Forward-Backward Reasoning and Prophecy