Abstract
Let Φ 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 Φ. 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.
Original language | English |
---|---|
Pages (from-to) | 1471-1509 |
Number of pages | 39 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 26 |
Issue number | 4 |
DOIs | |
Publication status | Published - 31 Dec 2012 |
Externally published | Yes |
Keywords
- Belief propagation
- K-SAT
- Phase transitions
- Random structures