Belief propagation on the random k-SAT model

Amin Coja-Oghlan; Noela Müller; Jean B. Ravelomanana

doi:10.1214/21-AAP1772

Belief propagation on the random k-SAT model

Amin Coja-Oghlan, Noela Müller, Jean B. Ravelomanana

Probability

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

23 Downloads (Pure)

Abstract

Corroborating a prediction from statistical physics, we prove that the belief propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as “replica symmetry” in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.

Original language	English
Pages (from-to)	3718-3796
Number of pages	79
Journal	Annals of Applied Probability
Volume	32
Issue number	5
DOIs	https://doi.org/10.1214/21-AAP1772
Publication status	Published - Oct 2022

Funding

Funding. The first author was supported by DFG CO 646/3 and DFG CO 646/4. The second author was supported in part by ERC-Grant 772606-PTRCSP. The third author was supported by DFG CO 646/4.

Funders	Funder number
International Advisory Board of ERC Advanced Grant Project THUNDERR	772606-PTRCSP
European Union's Horizon 2020 - Research and Innovation Framework Programme	772606
Deutsche Forschungsgemeinschaft	CO 646/4, CO 646/3

Keywords

belief propagation
k-SAT
phase transition
replica symmetry breaking

Access to Document

10.1214/21-AAP1772

pdfFinal published version, 838 KBLicence: TAVERNE

Cite this

@article{5cd862c42fc04c0b9b3e825272e0831f,

title = "Belief propagation on the random k-SAT model",

abstract = "Corroborating a prediction from statistical physics, we prove that the belief propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as “replica symmetry” in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.",

keywords = "belief propagation, k-SAT, phase transition, replica symmetry breaking",

author = "Amin Coja-Oghlan and Noela M{\"u}ller and Ravelomanana, \{Jean B.\}",

year = "2022",

month = oct,

doi = "10.1214/21-AAP1772",

language = "English",

volume = "32",

pages = "3718--3796",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "5",

}

TY - JOUR

T1 - Belief propagation on the random k-SAT model

AU - Coja-Oghlan, Amin

AU - Müller, Noela

AU - Ravelomanana, Jean B.

PY - 2022/10

Y1 - 2022/10

N2 - Corroborating a prediction from statistical physics, we prove that the belief propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as “replica symmetry” in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.

AB - Corroborating a prediction from statistical physics, we prove that the belief propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as “replica symmetry” in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.

KW - belief propagation

KW - k-SAT

KW - phase transition

KW - replica symmetry breaking

UR - http://www.scopus.com/inward/record.url?scp=85141329820&partnerID=8YFLogxK

U2 - 10.1214/21-AAP1772

DO - 10.1214/21-AAP1772

M3 - Article

AN - SCOPUS:85141329820

SN - 1050-5164

VL - 32

SP - 3718

EP - 3796

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 5

ER -

Belief propagation on the random k-SAT model

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this