@inproceedings{f6a0960e70eb4e1ab519b84e06d9fd99,
title = "Proof of the satisfiability conjecture for large k",
abstract = "We establish the satisfiability threshold for random k-SAT for all k ≥ k0. That is, there exists a limiting density αs(k) such that a random k-SAT formula of clause density α is with high probability satisfiable for α < αs, and unsatisfiable for α > αs. The satisfiability threshold αs(k) is given explicitly by the one-step replica symmetry breaking (1rsb) prediction from statistical physics. We believe that our methods may apply to a range of random constraint satisfaction problems in the 1RSB class.",
keywords = "Belief propagation, Condensation, Constraint satisfaction problem, Random k-SAT, Replica symmetry breaking, Satisfiability threshold, Survey propagation",
author = "Jian Ding and Allan Sly and Nike Sun",
year = "2015",
month = jun,
day = "14",
doi = "10.1145/2746539.2746619",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "59--68",
booktitle = "STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing",
note = "47th Annual ACM Symposium on Theory of Computing, STOC 2015 ; Conference date: 14-06-2015 Through 17-06-2015",
}