Survey Propagation Revisited
  Survey propagation (SP) is an exciting new technique that has been remarkably
successful at solving very large hard combinatorial problems, such as
determining the satisfiability of Boolean formulas. In a promising attempt at
understanding the success of SP, it was recently shown that SP can be viewed as
a form of belief propagation, computing marginal probabilities over certain
objects called covers of a formula. This explanation was, however, shortly
dismissed by experiments suggesting that non-trivial covers simply do not exist
for large formulas. In this paper, we show that these experiments were
misleading: not only do covers exist for large hard random formulas, SP is
surprisingly accurate at computing marginals over these covers despite the
existence of many cycles in the formulas. This re-opens a potentially simpler
line of reasoning for understanding SP, in contrast to some alternative lines
of explanation that have been proposed assuming covers do not exist.
