Nike Sun: The Exact k-SAT Threshold for Large k

We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k(0). That is, there exists a single critical density alpha_s(k) such that a random k-SAT formula of clause density alpha is with high probability satisfiable for alpha < alpha_s(k), and unsatisfiable for alpha > alpha_s(k). The threshold alpha_s(k) matches the explicit prediction derived by statistical physicists on the basis of the so-called `one-step replica symmetry breaking' (1RSB) heuristic. In the talk I will explain the main obstacles in computing the threshold, and describe how they are overcome in our proof. No prior background in statistical physics will be assumed.

Joint work with Jian Ding and Allan Sly.