The Decimation Process in Random $k$-SAT
Amin Coja-Oghlan, Angélica Pachón · SIAM Journal on Discrete Mathematics · 2012
Let $\boldsymbol{\Phi}$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. Nonrigorous statistical mechanics ideas have inspired a message passing algorithm called belief propagation guided decimation for finding satisfying assignments of $\boldsymbol{\Phi}$. This algorithm can be viewed as an attempt at implementing a certain thought experiment that we call the decimation process. In this paper we identify a variety of phase transitions in the decimation process and link these phase transitions to the performance of the algorithm.