skip to content

The exact $k$-SAT threshold for large $k$

Thursday 23rd April 2015 - 15:30 to 16:30
INI Seminar Room 1
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 $\alpha_*(k)$ such that a random $k$-SAT formula at clause-to-variable ratio $\alpha$ is with high probability satisfiable for $\alpha$ less than $\alpha_*(k)$, and unsatisfiable for $\alpha$ greater than $\alpha_*(k)$. The threshold $\alpha_*(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.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons