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

Nike Sun, MIT

The exact k-SAT threshold for large k

Abstract:

We establish the satisfiability threshold for random *k*-SAT for all *k* ≥ *k*_{0}. 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.