By Nike SUN, 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 c*(k) such that a random k-SAT formula at clause-to-variable ratio c is with high probability satisfiable for c < c*(k), and unsatisfiable for c > c*(k). The threshold c*(k) matches the explicit prediction derived by statistical physicists on the basis of the so-called "one-step replica symmetry breaking" (1RSB) heuristic. In the talk I will describe the main obstacles in computing the threshold, and indicate how they are overcome in our proof.

Joint work with Jian Ding and Allan Sly.