Analytic and Algorithmic Solution of Random Satisfiability Problems

By Marc Mézard, Giorgio Parisi, R. Zecchina. Science, 2002

1,008 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/bed19807ad7676a8897526329b0aa705203f079e

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 Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “The survey propagation algorithm, developed in the statistical physics community [168, 167], turns out to be very successful in solving random instances of 3-SAT.”
MAX k-CUT and approximating the chromatic number of random graphs (2006, methodology): “The present paper presents a reformulation of the 1RSB cavity method computation of [23, 24], in which no physics background is assumed.”
Critical phenomena in complex networks (2007, background): “…there were sparse graph error correcting codes (see, e.g., Montanari (2005) and references therein), phase transitions in random satisfiability problems (Achlioptas et al., 2005; Krza̧ka la et al., 2007; Mertens et al., 2003; Mézard et al., 2002), and combinatorial auctions (Galla et al., 2006).”
The mean field traveling salesman and related problems (2010, background): “Some important achievements in this direction are David Aldous’ proof of the ζ(2) limit in the assignment problem [4], Michel Talagrand’s proof of the correctness of the Parisi solution of the Sherrington–Kirkpatrick model [19], [34], [40], [44], and the algorithmic and theoretical results on phase ”
Statistical mechanics of complex neural systems and high dimensional data (2013, background): “4, statistical mechanics based approaches have inspired a new algorithm, known as survey propagation [77, 78], which can find good solutions despite the proliferation of metastable states whose presence can confound simpler optimization and inference algorithms.”
An almost-bijective proof of an asymptotic property of partitions (2007, background): “In spite of compelling arguments, however, from statistical physics [25, 26], and rigorous upper and lower bounds on the threshold if it exists [11, 18, 23], there is still no mathematical proof that a phase transition takes place at that density.”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “This notion of averaging over disorder is so well incrusted into a physicist mind that going away from this framework and starting to use the related (replica and cavity) calculations for a single realization of the disorder has lead to a major paradigm shift and to a development of revolutionary al”
Statistical Relational Artificial Intelligence: Logic, Probability, and Computation (2016, background): “In turns out that message-passing algorithm for solving SAT auch as namely warning propagation (WP) and survey propagation (SP) [Mézard et al., 2002], can be viewed as a form of belief propagation [Braunstein and Zecchina, 2004] and, hence, are amenable to lifting, too.”
On the solution-space geometry of random constraint satisfaction problems (2006, methodology): “Casting SP as an attempt to compute marginals over cores was done independently by Braunstein and Zecchina in [8] and Maneva, Mossel, and Wainwright in [19].”
Constraint satisfaction problems and neural networks: A statistical physics perspective. (2008, methodology): “This threshold behavior is nothing but a phase transition as one finds in physics, and has been analyzed using the methods of statistical physics (Kirkpatrick and Selman, 1994; Monasson et al., 1999; Mézard et al., 2003).”