[Combprob] This Wednesday at 10:30: Nike Sun (MIT) "The exact k-SAT threshold for large k"

[Daniel Spielman]

This talk is taking place at an unusual time and place.
It will be Oct 28 at 10:30 in DL 431.

*Oct 28: Nike Sun (MIT) 10:30 in DL 431:* "The exact k-SAT threshold for
large k"

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 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/combprob/attachments/20151025/ae54da54/attachment.html