Allender's Conjecture and its Impacts on Meta-Complexity
summary
Allender’s conjectures are shown false under plausible collapses: reductions to Kolmogorov-random strings would imply EXP^NP = NEXP, so the hoped characterization of BPP/NEXP fails unless that collapse occurs. Concrete results construct polynomial/nonadaptive oracle reductions and use symmetry of information plus a k-wise direct product generator and reconstruction to turn Kolmogorov queries into compressed certificates, yielding NP hardness and average-case/GapMINKT^PH equivalences and a conditional hardness of NP from UP not in DTIME(2^{O(n/log n)}).
AI-written summary · about
chapters (9)
- 0:00Start
- 1:37"Randomness" in Complexity and Computability
- 3:27Formal Definition and Universality
- 6:19Complexity vs. Computability Theory
- 7:13Reductions to Kolmogorov-random strings
- 14:09Complexity Classes
- 15:10Exponential-Time Classes
- 31:15Two mysteries of complexity theory
- 33:28Meta-Complexity - Complexity of Complexity
related talks
21mBlack-box Constructive Proofs are Unavoidable
01h 02mConsistency of NEXP Not in P/poly in a Strong Theory
57mTowards P≠NP from Extended Frege Lower Bounds
29mAssumptions in cryptography and complexity theory
49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
55mNon-commutative Computation
22mNew Lower Bounds and Derandomization for ACC, and a...
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic