Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

on YouTube ↗24m

" summary

Shows that for any dense-enough sparse random max-CSP the optimal satisfiable fraction equals a random-assignment baseline plus an explicit 1/√α second-order term equal to the ground-state energy density of a spin-glass whose mixture polynomial is the predicate’s noise-stability. Proof uses Poissonization, a generalized Guerra-Toninelli interpolation and multi-overlap coupling to transfer branching OGP geometry from spin glasses, yielding that overlap-concentrated algorithms (including local classical/quantum and bounded-round AMP families) cannot beat the ALG threshold.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 5:33Results
3. 8:55corollaries
4. 10:50informal definitions
5. 15:10proof ideas
6. 17:37optimal values
7. 18:53key insights
8. 21:35open questions

" related talks

• 26mTight Algorithmic Thresholds for Spin Glass HamiltoniansMark Sellke · Rigorous Evidence for Information-Computation Trade-offs
• 33mOptimization of Full-RSB Spherical Spin GlassesEliran Subag · Computational Phase Transitions (Simons Institute, 2020)
• 46mPhase Transitions in Random CSPsNike Sun · Random Instances and Phase Transitions (Simons Institute, 2016)
• 58mSmoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And CertificatesPravesh K. Kothari · Rigorous Evidence for Information-Computation Trade-offs
• 49mExtremal Cuts of Sparse Random GraphsAmir Dembo · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013
• 51mMin-max Optimization: From Complexity to AlgorithmsEmmanouil Zampetakis · Adversarial Approaches in Machine Learning 2022
• 44mAlgorithmic Pirogov-Sinai TheoryTyler Helmuth · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)