Abstract

Co-authors: Jian Ding (University of Chicago), Allan Sly (University of California—Berkeley)

We establish the random $k$-SAT threshold conjecture for all $k$ exceeding an absolute constant $k_0$. That is, there is a single critical value $lpha_$ such that a random $k$-SAT formula at clause-to-variable ratio $lpha$ is with high probability satisfiable for $lpha$ less than $lpha_(k)$, and unsatisfiable for $lpha$ greater than $lpha_$. The threshold $lpha_(k)$ matches the explicit prediction derived by statistical physicists on the basis of the one-step replica symmetry breaking (1RSB) heuristic. In the talk I will describe the main obstacles in computing the threshold, and explain how they are overcome in our proof. Joint work with Jian Ding and Allan Sly.