Nike Sun: The Exact k-SAT Threshold for Large k

Tuesday, December 1, 2015 - 4:15pm to 5:15pm
Light Refreshments at 3:50pm
Patil/Kiva G449
Nike Sun
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), and unsatisfiable for c > c*(k). The threshold c*(k) matches the explicit prediction derived by statistical physicists on the basis of the so-called "one-step replica symmetry breaking" (1RSB) heuristic. In the talk I will describe the main obstacles in computing the threshold, and indicate how they are overcome in our proof. (No prior background in statistical physics will be assumed.)
Joint work with Jian Ding and Allan Sly.