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

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

• Sun, N (Massachusetts Institute of Technology)
• Thursday 23 April 2015, 15:30-16:30
• Seminar Room 1, Newton Institute.

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

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.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.