Survey propagation: An algorithm for satisfiability

By Alfredo Braunstein, M. M'ezard, Riccardo Zecchina. 2002

539 citations recorded by the source corpus.

We study the satisfiability of randomly generated formulas formed by M clauses of exactly K literals over N Boolean variables. For a given value of N the problem is known to be most difficult when α = M/N is close to the experimental threshold αc separating the region where almost all formulas are SAT from the region where all formulas are UNSAT. Recent results from a statistical physics analysis suggest that the difficulty is related to the existence of a clustering phenomenon of the solutions when α is close to (but smaller than) αc. We introduce a new type of message passing algorithm which allows to find efficiently a satisfying assignment of the variables in this difficult region. This algorithm is iterative and composed of two main parts. The first is a message‐passing procedure which generalizes the usual methods like Sum‐Product or Belief Propagation: It passes messages that may be thought of as surveys over clusters of the ordinary messages. The second part uses the detailed probabilistic information obtained from the surveys in order to fix variables and simplify the problem. Eventually, the simplified problem that remains is solved by a conventional heuristic. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Entropy-SGD: biasing gradient descent into wide valleys (2016, background): “Introducing non-local terms in classical inference techniques for these problems has led to state-of-the-art algorithms (Braunstein et al., 2005; Maneva et al., 2007).”
Learning a SAT Solver from Single-Bit Supervision (2018, methodology): “Survey Propagation (SP) is a message passing algorithm for SAT that is not used in practice but that is similar to NeuroSAT in that continuous-valued messages are iteratively passed between literals and the clauses they occur in (Braunstein et al., 2005).”
Using Expectation Maximization to Find Likely Assignments for Solving CSP's (2007, background): “First is a parameter governing the size of a single decimation [4].”
A quantitative study of irregular programs on GPUs (2012, methodology): “Irregular programs can be found in domains like n-body simulation [5], data mining [44], decisions problems that use Boolean satisfiability [6], optimization theory [12], social networks [23], system modeling [39], compilers [1], discrete-event simulation [35], and meshing [11].”
The Effect of Gradient Noise on the Energy Landscape of Deep Networks (2015, background): “…of spin glasses to combinatorial optimization, random k-SAT, LDPC codes etc. have become popular (Mezard and Montanari, 2009) and an understanding of the energy landscape and thermodynamics of such systems has led to a number of efficient algorithms (Krzakala et al., 2011; Braunstein et al., 2005).”
Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “Survey propagation turns out to be an instance of the sum-product or belief propagation algorithm, but as applied to an alternative graphical model for satisfiability problems [38, 159].”
Polar Codes for Channel and Source Coding (2009, methodology): “The encoding was therefore done using survey propagation inspired decimation (SID), an algorithm used for finding solutions of a k-SAT formula [43].”
A new look at survey propagation and its generalizations (2004, methodology): “As shown in [ 4 ], setting � = 0 yields the belief propagation updates applied to the probability distribution (2), whereas setting � = 1 yields the pure version of survey propagation.”
Dependency Parsing by Belief Propagation (2008, methodology): “Our method and its numerical details emerge naturally as an instance of the well-studied loopy BP algorithm, suggesting several future improvements to accuracy (Yedidia et al., 2004; Braunstein et al., 2005) and efﬁciency (Sutton and McCallum, 2007).”
The threshold for random k-SAT is 2^k log 2 - O(k) (2004, methodology): “Insights from this analysis led them to an intriguing algorithm called “survey propagation” (described in [21, 2]) that seems to perform well on random instances of k -SAT close to the threshold, at least for small k .”
Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes (2016, background): “[39] Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina.”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, unknown): “They rely on the following linear integer program, which can be shown to be equivalent to the task of minimizing the MRF energy (1) [40], [7], [53]: min x Eð ; xÞ ¼ Áx ¼ X p2V p Áx p þ X pq2E pq Áx pq ; s:t: x 2 X G ;”
Information Theory, Inference, and Learning Algorithms (2004, background): “Interesting message-passing algorithms that have different capabilities from the sum–product algorithm include expectation propagation (Minka, 2001) and survey propagation (Braunstein et al., 2003).”