pdf icon
Volume 9 (2013) Article 19 pp. 617-651
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
Received: January 22, 2012
Revised: May 4, 2013
Published: June 15, 2013
Download article from ToC site:
[PDF (399K)]    [PS (1674K)]    [PS.GZ (430K)]
[Source ZIP]
Keywords: constraint satisfaction, average case, SAT, statistical physics
ACM Classification: F.2.2, G.3
AMS Classification: 68Q25, 90C59

Abstract: [Plain Text Version]

$ \newcommand{\PlantedDist}{{\textsf{P}}^{{\rm plant}}_{n,p}} \newcommand{\RandDist}{{\textsf{P}}_{n,p}} \newcommand{\RandDistSat}{{\textsf{P}}^{{\rm sat}}_{n,p}} \newcommand{\F}{{\textsf{F}}} \newcommand{\Core}{{\textsf{H}}} \newcommand{\WP}{\textsf{WP}} $

In this paper we analyze the performance of Warning Propagation, a popular message passing algorithm. We show that for 3CNF formulas drawn from a certain distribution over random satisfiable 3CNF formulas, commonly referred to as the planted-assignment distribution, running Warning Propagation in the standard way (run message passing until convergence, simplify the formula according to the resulting assignment, and satisfy the remaining subformula, if necessary, using a simple “off the shelf” heuristic) works when the clause-variable ratio is a sufficiently large constant. We are not aware of previous rigorous analysis showing the effectiveness of message passing algorithms for satisfiability instances.

An extended abstract of this paper appeared in the Proceedings of RANDOM 2006.