ACO The ACO Seminar (2014–2015)

Jan. 21 and Jan. 23, 3:30pm, Wean 8220   (Note 2-day lecture series on unusual days)
Nike Sun, MIT
The exact k-SAT threshold for large k


We establish the satisfiability threshold for random k-SAT for all kk0. That is, there exists a limiting density αs(k) such that a random k-SAT formula of clause density alpha is with high probability satisfiable for α < αs(k), and unsatisfiable for α > αs(k). The satisfiability threshold αs(k) is given explicitly by the one-step replica symmetry breaking prediction from statistical physics.

Joint work with Jian Ding and Allan Sly.

Back to the ACO home page