##### 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****************************