The decimation process in random k-SAT

Amin Coja-Oghlan; Angelica Pachon

doi:10.1007/978-3-642-22006-7_26

The decimation process in random k-SAT

Amin Coja-Oghlan^*, Angelica Pachon

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

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 language	English
Title of host publication	Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Pages	305-316
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-22006-7_26
Publication status	Published - 11 Jul 2011
Externally published	Yes
Event	38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland Duration: 4 Jul 2011 → 8 Jul 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6755 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	38th International Colloquium on Automata, Languages and Programming, ICALP 2011
Country/Territory	Switzerland
City	Zurich
Period	4/07/11 → 8/07/11

Access to Document

10.1007/978-3-642-22006-7_26Licence: CC BY-NC-ND

Cite this

Coja-Oghlan, A., & Pachon, A. (2011). The decimation process in random k-SAT. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings (PART 1 ed., pp. 305-316). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6755 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-22006-7_26

@inproceedings{1b14c1dcb25c448bb34878edd8f4d484,

title = "The decimation process in random k-SAT",

abstract = "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.",

author = "Amin Coja-Oghlan and Angelica Pachon",

year = "2011",

month = jul,

day = "11",

doi = "10.1007/978-3-642-22006-7_26",

language = "English",

isbn = "9783642220050",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "305--316",

booktitle = "Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings",

edition = "PART 1",

note = "38th International Colloquium on Automata, Languages and Programming, ICALP 2011 ; Conference date: 04-07-2011 Through 08-07-2011",

}

Coja-Oghlan, A & Pachon, A 2011, The decimation process in random k-SAT. in Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6755 LNCS, pp. 305-316, 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, Zurich, Switzerland, 4/07/11. https://doi.org/10.1007/978-3-642-22006-7_26

The decimation process in random k-SAT. / Coja-Oghlan, Amin; Pachon, Angelica.
Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1. ed. 2011. p. 305-316 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6755 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The decimation process in random k-SAT

AU - Coja-Oghlan, Amin

AU - Pachon, Angelica

PY - 2011/7/11

Y1 - 2011/7/11

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-22006-7_26

DO - 10.1007/978-3-642-22006-7_26

M3 - Conference contribution

AN - SCOPUS:79959953456

SN - 9783642220050

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 305

EP - 316

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011

Y2 - 4 July 2011 through 8 July 2011

ER -

The decimation process in random k-SAT

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this