@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",

}