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

Date:
Thursday 23rd April 2015 - 15:30 to 16:30
Venue:
INI Seminar Room 1
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 $\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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.