Printable PDF
Department of Mathematics,
Department of Mathematics,
University of California San Diego
****************************
Math 268 - Computability and Logic
Nicholas Sieger
UC San Diego
The Satisfiability Threshold in Random k-SAT
Abstract:
Consider a uniformly random k-SAT instance with a fixed ratio of the number of clauses to the number of variables. As the clause-variable ratio increases, a curious phenomenon appears. With high probability the random instance is satisfiable below a certain threshold and unsatisfiable above the same threshold. This talk will give an overview of the problem of determining the precise threshold for random k-SAT, including various algorithmic approaches, the connections to statistical physics, Friedman's sharp threshold theorem, and the determination of the k-SAT threshold for large k by Ding, Sun, and Sly in 2014.
February 12, 2024
4:00 PM
APM 7218
Research Areas
Logic and Computational Complexity****************************
