The Exact k-SAT Threshold for Large k
Monday, March 16, 2015 - 11:20am - 12:00pm
Klaus 2443
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.
Joint work with Jian Ding and Allan Sly.