Belief and Survey Propagation

on YouTube ↗01h 18m

" summary

Experimental survey propagation beats classic solvers on random 4‑SAT but later analysis shows the message‑passing decimation idea stalls roughly a factor K below the satisfiability threshold (threshold ~2^K log 2, clustering at ~2^K log K / K). Heuristic physics formulas become a closed variational problem; the interpolation and second‑moment techniques prove the threshold prediction for large K (Ding‑Sly‑Sun), while belief propagation is shown to correctly approximate marginals and counts for random 2‑SAT up to density 1.

AI-written summary · about

" chapters (12)

1. 0:00Introduction
2. 1:03Physics and algorithms
3. 4:30Phase transitions
4. 7:21Early analysis methods
5. 12:04Connections to physics
6. 16:40Clustering and geometry
7. 23:26Belief propagation
8. 31:24Survey propagation
9. 35:25Rigorous methods
10. 37:57Algorithmic applications
11. 45:00Results for 2-SAT
12. 47:25Discussion and Q&A