A new look at survey propagation and its generalizations
- 1 July 2007
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 54 (4), 17
- https://doi.org/10.1145/1255443.1255445
Abstract
This article 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 ρ ∈ [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 (ρ = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (ρ = 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 ρ = 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 ρ < 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 ρ > 0 can be viewed as a “smoothed” version of the uniform distribution over satisfying assignments (ρ = 0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of k -SAT problems.Keywords
Other Versions
This publication has 23 references indexed in Scilit:
- Glauber dynamics on trees and hyperbolic graphsProbability Theory and Related Fields, 2004
- Survey propagation as local equilibrium equationsJournal of Statistical Mechanics: Theory and Experiment, 2004
- Analytic and Algorithmic Solution of Random Satisfiability ProblemsScience, 2002
- CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief PropagationNeural Computation, 2002
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Factor graphs and the sum-product algorithmIEEE Transactions on Information Theory, 2001
- A remark on random 2-SATDiscrete Applied Mathematics, 1999
- The probability of pure literalsJournal of Logic and Computation, 1999
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- Approximating probabilistic inference in Bayesian belief networks is NP-hardArtificial Intelligence, 1993