University of Cambridge > > Isaac Newton Institute Seminar Series > The exact $k$-SAT threshold for large $k$

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

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Random Geometry

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2022, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity