Proof of the satisfiability conjecture for large \(k\) (Q2171413): Difference between revisions

In this major paper, the authors derive a sharp threshold for the random \(k\)-sat problem, for the parameter \(k\) chosen large enough. They identify the threshold separating the satisfiable and the unsatisfiable regimes, and prove there is a sharp transition. In the proof they develop and apply a refined moment method, and justify the 1-RSB (one-step Replica-Symmetry-Breaking) answer which was predicted by nonrigorous physics methods originating in spin-glass theory. They reduce the problem to analysing a tree recurrence problem. The authors have spent a lot of effort in making the paper accessible and reasonably self-contained, providing earlier results, both rigorous and nonrigorous, and giving intuition and background. It makes the paper long (and a long time in finalising in view of the time between submission and publication), but it appears as an impressive accomplishment.