TCS+ Talk
Available remotely at Google Hangouts:
https://sites.google.com/site/plustcs/
Abstract:
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 \alpha_c(k) such that a random k-SAT formula at clause-to-variable
ratio \alpha is with high probability satisfiable for
\alpha<\alpha_c(k), and unsatisfiable for \alpha>\alpha_c(k). The
threshold \alpha_c(k) matches the explicit prediction derived by
statistical physicists on the basis of the one-step replica symmetry
breaking (1RSB) heuristic.
exceeding an absolute constant k_0. That is, there is a single critical
value \alpha_c(k) such that a random k-SAT formula at clause-to-variable
ratio \alpha is with high probability satisfiable for
\alpha<\alpha_c(k), and unsatisfiable for \alpha>\alpha_c(k). The
threshold \alpha_c(k) matches the explicit prediction derived by
statistical physicists on the basis of the one-step replica symmetry
breaking (1RSB) heuristic.
Joint work with Jian Ding and Nike Sun.
For more information, please contact Thomas Vidick by email at [email protected].
Event Series
TCS+ Talks