The Exact k-SAT Threshold for Large k

Tuesday, May 19, 2015 - 2:00pm - 2:50pm
Keller 3-180
Nike Sun (Microsoft Research)
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 c_*(k) such that a random k-SAT formula at clause-to-variable ratio c is with high probability satisfiable for c c_*(k). The threshold c_*(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.
MSC Code: