  This paper provides a new conceptual perspective on survey propagation, which
is an iterative algorithm recently introduced by the statistical physics
community that is very effective in solving random k-SAT problems even with
densities close to the satisfiability threshold. We first describe how any SAT
formula can be associated with a novel family of Markov random fields (MRFs),
parameterized by a real number \rho \in [0,1]. We then show that applying
belief propagation--a well-known ``message-passing'' technique for estimating
marginal probabilities--to this family of MRFs recovers a known family of
algorithms, ranging from pure survey propagation at one extreme (\rho = 1) to
standard belief propagation on the uniform distribution over SAT assignments at
the other extreme (\rho = 0). Configurations in these MRFs have a natural
interpretation as partial satisfiability assignments, on which a partial order
can be defined. We isolate cores as minimal elements in this partial ordering,
which are also fixed points of survey propagation and the only assignments with
positive probability in the MRF for \rho=1. Our experimental results for k=3
suggest that solutions of random formulas typically do not possess non-trivial
cores. This makes it necessary to study the structure of the space of partial
assignments for \rho<1 and investigate the role of assignments that are very
close to being cores. To that end, we investigate the associated lattice
structure, and prove a weight-preserving identity that shows how any MRF with
\rho>0 can be viewed as a ``smoothed'' version of the uniform distribution over
satisfying assignments (\rho=0). Finally, we isolate properties of Gibbs
sampling and message-passing algorithms that are typical for an ensemble of
k-SAT problems.
