The decimation process in random k-SAT

Amin Coja-Oghlan*, Angelica Pachon

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

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 languageEnglish
Pages (from-to)1471-1509
Number of pages39
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number4
DOIs
Publication statusPublished - 31 Dec 2012
Externally publishedYes

Keywords

  • Belief propagation
  • K-SAT
  • Phase transitions
  • Random structures

Fingerprint

Dive into the research topics of 'The decimation process in random k-SAT'. Together they form a unique fingerprint.

Cite this