On Oracles and Algorithmic Methods for Proving Lower Bounds

on YouTube ↗16m

" summary

Proves an equivalence between missing string circuit complexity and whether Σ2E requires exponential-size circuits relative to every oracle, constructs uniform depth-4 circuits for the problem while ruling out depth-2, and shows local algorithms that compute any output bit with O(k log k) probes when M ≤ k·N (with a matching Ω(k) lower bound). Also gives two separate oracle separations showing the algorithmic method for circuit lower bounds does not relativize. Open: whether small uniform depth-3 circuits exist.

AI-written summary · about

" chapters (5)

1. 0:00Introduction to sub-papers
2. 3:41The algorithm method
3. 5:42Missing string problem
4. 11:03Local algorithms for strings
5. 15:04Conclusion and open problems

" related talks

• 52mThe Mystery of the Missing StringRyan Williams · Lower Bounds, Learning, and Average-Case Complexity
• 01h 01mTop-Down Lower Bounds for Depth-Four CircuitsMika Göös · Structural Results 2023
• 19mAlgorithms and Lower Bounds for Comparator Circuits from ShrinkageBruno P. Cavalar, Zhenjian Lu · ITCS 2022
• 47mHardness Amplification and the Approximate Degree of Constant-Depth CircuitsJustin Thaler · Neo-Classical Methods in Discrete Analysis 2013
• 01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional ExpandersMax Hopkins · Beyond the Boolean Cube 2023
• 49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the CircuitDan Suciu · Probabilistic Circuits and Logic 2023
• 51mAllender's Conjecture and its Impacts on Meta-ComplexityShuichi Hirahara · Lower Bounds, Learning, and Average-Case Complexity
• 37mJourney with Eric Allender: From Turing Machines to Circuits, and BackMichal Koucky · Lower Bounds, Learning, and Average-Case Complexity