Random Constraint Satisfaction Problems
summary
Random k‑SAT has a sharp satisfiability threshold predicted by the physics one‑step replica symmetry breaking formula and proven for sufficiently large k; the proof strategy maps clusters of solutions to Belief‑Propagation fixed points, then projects those measures to warning propagation (+, −, free) combinatorial configurations, showing the first/second‑moment failures come from first moment threshold domination by atypical clusters and that typical instances condense into a bounded number of large clusters whose statistics determine the exact threshold.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:49The SAT problem The boolean satisfiability (SAT) problem
- 1:27Constraint satisfaction problems
- 4:29SAT threshold conjecture
- 6:05Friedgut's theorem
- 8:55First moment
- 12:57Statistical physics of random CSPs
- 16:14The 1RSB threshold
- 17:19Moment method and 1RSB
- 20:44RS(B) in graphical models
- 25:26Clusters of solutions
- 30:30Cluster complexity function
- 36:37Definition of 1RSB
- 39:241RSB formulas
- 43:16Cavity measure and fixed points
- 51:40Combinatorial cluster encoding
- 55:06Open questions
related talks
01h 17mInapproximability of Constraint Satisfaction Problems III
50mRandom Combinatorial Matrices
01h 30mInapproximability of Constraint Satisfaction Problems II
27mA Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 17mInapproximability of Constraint Satisfaction Problems V
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
48mUnstructured Hardness to Average-Case Randomness