BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The exact $k$-SAT threshold for large $k$ - Sun\, N (Massachusetts
  Institute of Technology)
DTSTART:20150423T143000Z
DTEND:20150423T153000Z
UID:TALK59086@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Co-authors: Jian Ding (University of Chicago)\, Allan Sly (Uni
 versity of California--Berkeley)\n\nWe establish the random $k$-SAT thresh
 old conjecture for all $k$ exceeding an absolute constant $k_0$. That is\,
  there is a single critical value $lpha_*(k)$ such that a random $k$-SAT 
 formula at clause-to-variable ratio $lpha$ is with high probability satis
 fiable for $lpha$ less than $lpha_*(k)$\, and unsatisfiable for $lpha$ 
 greater than $lpha_*(k)$. The threshold $lpha_*(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 t
 he main obstacles in computing the threshold\, and explain how they are ov
 ercome in our proof. Joint work with Jian Ding and Allan Sly.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR