The decimation process in random k-SAT

Amin Coja-Oghlan*, Angelica Pachon

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)


Non-rigorous statistical mechanics ideas have inspired a message passing algorithm called Belief propagation guided decimation for finding satisfying assignments of random k-SAT instances. 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
Title of host publicationAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Number of pages12
EditionPART 1
Publication statusPublished - 11 Jul 2011
Externally publishedYes
Event38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland
Duration: 4 Jul 20118 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6755 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference38th International Colloquium on Automata, Languages and Programming, ICALP 2011


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

Cite this