Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

The exact k-SAT threshold for large k

February 27, 2015 @ 11:00 am

Nike Sun (MSR New England and MIT Mathematics)


We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k0. That is, there is a single critical value α∗(k) such that a random k-SAT formula at clause-to-variable ratio α is with high probability satisfiable for αα∗(k). The threshold α∗(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.

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307