The ACO Seminar (2014–2015)

We establish the satisfiability threshold for random k-SAT for all k ≥ k₀. That is, there exists a limiting density α_s(k) such that a random k-SAT formula of clause density alpha is with high probability satisfiable for α < α_s(k), and unsatisfiable for α > α_s(k). The satisfiability threshold α_s(k) is given explicitly by the one-step replica symmetry breaking prediction from statistical physics.

Joint work with Jian Ding and Allan Sly.