Nike Sun: The Exact k-SAT Threshold for Large k

Friday, December 19, 2014 - 12:45pm to 3:45pm
Pizza at 12:30pm
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Nike Sun

We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k(0). That is, there exists a single critical density alpha_s(k) such that a random k-SAT formula of clause density alpha is with high probability satisfiable for alpha < alpha_s(k), and unsatisfiable for alpha > alpha_s(k). The threshold alpha_s(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 explain the main obstacles in computing the threshold, and describe how they are overcome in our proof. No prior background in statistical physics will be assumed.

Joint work with Jian Ding and Allan Sly.