Theory of Computing
-------------------
Title     : Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
Authors   : Uriel Feige, Elchanan Mossel, and Dan Vilenchik
Volume    : 9
Number    : 19
Pages     : 617-651
URL       : https://theoryofcomputing.org/articles/v009a019

Abstract
--------

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.