The Mystery of the Missing String

on YouTube ↗52m

" summary

Equivalence between the simple missing string task and relativized exponential lower bounds: finding a string outside M strings of length N (with M ≈ 2^{εN}) is shown to be tightly equivalent to whether σ2E needs 2^{εn}-size oracle circuits. A halving algorithm uses ~M total probes (one-probe when M ≤ N), and a k-probe tradeoff sits between k and Θ(k log k. The proof uses uniform quasi-polynomial depth-3 AC0 circuits for missing string, a normal form that encodes oracle behavior, and yields new time-hierarchy corollaries; the status of depth‑3 lower bounds remains open.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:50Stereo complexity
3. 2:10Smallest known class
4. 3:45Highlevel sketch
5. 6:52The missing string
6. 9:47Exponential Complexity
7. 13:46Missing String
8. 21:54Example
9. 30:54Generic Theorem
10. 37:22Why is there a tight connection
11. 41:05Local algorithms
12. 44:12Hierarchy theorems
13. 46:55Questions

" related talks

• 16mOn Oracles and Algorithmic Methods for Proving Lower BoundsRyan Williams, Nikhil Vyas · ITCS 2023
• 36mExponential Separation of Information and CommunicationGillat Kol · Information Theory in Complexity Theory and Combinatorics 2015
• 57mTowards P≠NP from Extended Frege Lower BoundsJán Pich · Proof Complexity and Meta-Mathematics 2023
• 19mAlgorithms and Lower Bounds for Comparator Circuits from ShrinkageBruno P. Cavalar, Zhenjian Lu · ITCS 2022
• 01h 02mConsistency of NEXP Not in P/poly in a Strong TheoryAlbert Atserias · Proof Complexity and Meta-Mathematics 2023
• 01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional ExpandersMax Hopkins · Beyond the Boolean Cube 2023
• 47mHardness Amplification and the Approximate Degree of Constant-Depth CircuitsJustin Thaler · Neo-Classical Methods in Discrete Analysis 2013
• 30mStreaming Lower Bounds for Approximating MAX-CUTMichael Kapralov · Information Theory in Complexity Theory and Combinatorics 2015