  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) results in a satisfying assignment
when the clause-variable ratio is a sufficiently large constant.
