Where the Hard Things Are
summary
Random K-SAT exhibits a sharp satisfiability threshold ~4.267 for k=3 and a geometry where solutions break into exponentially many well-separated clusters then condense to few. Rigorous progress uses moments, whitening to define clusters, and counting clusters rather than solutions; physics predicts exact thresholds. Algorithms use belief propagation and survey propagation and BP-guided decimation, which empirically and heuristically work up to about α ≈ 2^k / k while SDP and SOS give barriers around n^{k/2}.
AI-written summary · about
chapters (15)
- 0:00Start
- 0:43What Is Satisfiability
- 1:39Factor Graph
- 2:27Standard Mainstream Complexity Theory
- 9:25Satisfiability Conjecture
- 11:58Random Graph Coloring
- 13:33Structural Properties
- 14:13The Method of Moments
- 14:52The Moment Method
- 16:51Moment Method
- 41:49Planted Model
- 43:49The Nucleation Problems
- 50:16Belief Propagation in Artificial Intelligence
- 50:50Finding Solutions
- 1:03:14Uniform Probability Distribution of a Solution
related talks
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 17mInapproximability of Constraint Satisfaction Problems III
27mA Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
01h 17mInapproximability of Constraint Satisfaction Problems V
01h 30mInapproximability of Constraint Satisfaction Problems II
01h 01mThe Gospel According to TCS
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
23mSome New Results on Random Points in the Unit Square