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 k
. That is, there exists a limiting density αs
) such that a random k
-SAT formula of clause density alpha is with high probability satisfiable for α < αs
unsatisfiable for α > αs
). The satisfiability threshold αs
) 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