Counting Solutions to Random Constraint Satisfaction Problems
summary
Proves the free‑energy limit for a D‑regular NAE‑SAT model (binary, locally homogeneous) and shows it matches the one‑step replica‑symmetry‑breaking prediction: below the condensation threshold the typical log‑count equals the first‑moment value, but in the condensed regime the typical free energy is strictly smaller than the expectation. Key tools are the interpolation method for the upper bound, a tailored second‑moment argument using Z_lambda (clusters weighted by size), belief‑propagation fixed points on the tree and a high‑K regularity simplification.
AI-written summary · about
chapters (13)
- 0:00Introduction to CSPs
- 1:21Model definitions
- 3:42The Not-All-Equal SAT model
- 6:11Counting solutions
- 10:01Phase transitions
- 14:39One-step replica symmetry
- 17:23Geometry of the solution space
- 20:05Complexity and condensation
- 24:20Challenges in the condensed regime
- 27:35Explicit formulas for free energy
- 33:21Proof methods
- 37:32Belief propagation and weights
- 44:15Conclusion and Q&A
related talks
01h 17mPedagogical Talk: Random Optimisation Problems
20mFunction synthesis for maximizing model counting
41mCounting Solutions to Random CNF Formulas
24mA subpolynomial-time algorithm for the free energy of one-dimensional...
24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
10mSATisfying answers to difficult questions!
01h 18mStatistical Physics and Computation in High Dimension
01h 04m"More is Different." Also in Computing?