Phase Transitions in Random CSPs

on YouTube ↗46m

" summary

Random regular k-SAT on a bipartite factor graph gets a rigorous 1RSB free-energy: for large K the limit of (1/N) log Z exists in probability and matches an explicit function F coming from a telescoping cavity reduction plus tree computations. The proof computes cluster sizes via a Legendre dual of a tilted cluster sum, shows replica BP fixed-point Q laws govern boundary marginals, uses BP/dynamic programming on free-variable trees, and yields alpha_sat/alpha_cond thresholds and concentration of Z^lambda.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 4:48The Replica Symmetric Free Energy
3. 28:31Replica Symmetry within Clusters
4. 36:49Bp Formula

" related talks

• 24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin GlassesChris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi · ITCS 2023
• 58mSmoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And CertificatesPravesh K. Kothari · Rigorous Evidence for Information-Computation Trade-offs
• 44mAlgorithmic Pirogov-Sinai TheoryTyler Helmuth · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 01h 17mPedagogical Talk: Random Optimisation ProblemsAmin Coja-Oghlan · Computational Phase Transitions (Simons Institute, 2020)
• 41mCounting Solutions to Random CNF FormulasLeslie Ann Goldberg · Computational Phase Transitions (Simons Institute, 2020)
• 34mSampling From the Random Cluster Model at All Temperatures on Random GraphsWill Perkins · Computational Phase Transitions (Simons Institute, 2020)
• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013
• 59mLP/SDP Hierarchies and Sum of Squares Proofs 3Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017