We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k0. That is, there is a single critical value αsat(k) such that a random k-SAT formula sampled at clause-to-variable ratio α is with high probability satisfiable for α < αsat, and unsatisfiable for α > αsat. The satisfiability threshold αsat 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.
This is joint work with Jian Ding and Allan Sly.
The Probability Seminars are held in Sequoia Hall, Room 200, at 4:30pm on Mondays. Refreshments are served at 4pm in the Lounge on the first floor.