BELIEF PROPAGATION ON THE RANDOM k-SAT MODEL

• 成果类型: Article
• 署名作者: Coja-Oghlan, Amin; Mueller, Noela; Ravelomanan, Jean B.
• 署名单位: Dortmund University of Technology; Eindhoven University of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/21-AAP1772
• 发表日期: 2022
• 页码: 3718-3796
• 关键词: threshold; heuristics; number; STATES

摘要

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.