|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
MIT Title: The exact k-SAT threshold for large k, part 2 Abstract: We establish the satisfiability threshold for random k-SAT for all k ≥ k0. That is, there exists a limiting density αs(k) such that a random k-SAT formula of clause density alpha is with high probability satisfiable for α < αs(k), and unsatisfiable for α > αs(k). The satisfiability threshold αs(k) is given explicitly by the one-step replica symmetry breaking prediction from statistical physics. Joint work with Jian Ding and Allan Sly. |
