Some Easy Optimization Problems Have the Overlap-Gap Property
summary
Shows that some easy problems like S–T shortest path in Gn,Θ(log n)/n nevertheless satisfy an ensemble OGP: correlated graph sequences force near-optimal paths to be either almost identical or nearly disjoint, and this holds with probability 1 − O(1/ polylog n). Uses correlated-resampling constructions plus refined noise-stability bounds for low-degree polynomials to get hardness: Lipschitz algorithms and degree-D methods fail (success ≤ 2^{-Θ(D)}), yet a logarithmic-degree polynomial (deg ≈ log n / log log n) actually recovers the path with high probability.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:03Title and abstract
- 2:06Overlap-gap property explained
- 4:26Origins in physics and hardness
- 6:39Maximum independent set
- 8:28Ensemble OGP and Lipschitz algorithms
- 12:05Lower bounds for Lipschitz algorithms
- 16:52What are Lipschitz algorithms?
- 20:29Lower bounds for polynomials
- 22:41OGP as computational threshold
- 23:43Main result: shortest path
- 26:42Corollaries of main theorem
- 29:44Improving polynomial bounds
- 31:28Logarithmic degree algorithm
- 33:42Critique of assumptions
- 36:10Conclusion
related talks
36mThe Overlap Gap Property For Inference: Power And Limitations
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
54mExact Matching Of Random Graphs With Constant Correlation
01h 00mAverage-case Complexity for Polynomials, and All That
57mIt ain't over till it's over
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
49mRecent Advances in Counting Sparse Graphs