Events Fall 2014

TCS+ Online Seminar

Feb 18, 2015 10:00 am – 11:00 am 

Add to Calendar


Allan Sly (UC Berkeley)


Calvin Lab 116

Proof of the satisfiability conjecture for large k

We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k_0. That is, there is a single critical value \alpha_c(k) such that a random k-SAT formula at clause-to-variable ratio \alpha is with high probability satisfiable for \alpha<\alpha_c(k), and unsatisfiable for \alpha>\alpha_c(k). The threshold \alpha_c(k) matches the explicit prediction derived by statistical physicists on the basis of the one-step replica symmetry breaking (1RSB) heuristic. 

Joint work with Jian Ding and Nike Sun.