Survey propagation: An algorithm for satisfiability
From MaRDI portal
Publication:5318246
DOI10.1002/rsa.20057zbMath1087.68126OpenAlexW2950654313WikidataQ56431749 ScholiaQ56431749MaRDI QIDQ5318246
Riccardo Zecchina, Alfredo Braunstein, Marc Mézard
Publication date: 22 September 2005
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20057
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Related Items
A comparative runtime analysis of heuristic algorithms for satisfiability problems, A collaborative approach for multi-threaded SAT solving, Disordered systems insights on computational hardness, Satisfiability Thresholds beyond k −XORSAT, Statistical Physics and Network Optimization Problems, The solution space structure of planted constraint satisfaction problems with growing domains, Random Instances of Problems in NP – Algorithms and Statistical Physics, The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘), Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP, A Computing Procedure for Quantification Theory, The asymptotics of the clustering transition for random constraint satisfaction problems, Proof of the satisfiability conjecture for large \(k\), Maximum independent sets on random regular graphs, On the thresholds in linear and nonlinear Boolean equations, Tropical limit and a micro-macro correspondence in statistical physics, Why adiabatic quantum annealing is unlikely to yield speed-up, The asymptotic \(k\)-SAT threshold, Leveraging cluster backbones for improving MAP inference in statistical relational models, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, Understanding science through the computational lens, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, The consequences of eliminating NP solutions, Message-passing algorithms for inference and optimization, Anomalous scaling of the optimal cost in the one-dimensional random assignment problem, Investigation of commuting Hamiltonian in quantum Markov network, Statistical mechanics of complex neural systems and high dimensional data, Local search for Boolean satisfiability with configuration checking and subscore, Low-temperature excitations within the Bethe approximation, Lowering the error floor of Gallager codes: a statistical-mechanical view, Local entropy as a measure for sampling solutions in constraint satisfaction problems, The large deviations of the whitening process in random constraint satisfaction problems, On one-step replica symmetry breaking in the Edwards–Anderson spin glass model, Circular coloring of random graphs: statistical physics investigation, Satisfiability threshold for power law random 2-SAT in configuration model, A Spectral Approach to Analysing Belief Propagation for 3-Colouring, The Decimation Process in Random k-SAT, Pairs of SAT-assignments in random Boolean formulæ, A review of message passing algorithms in estimation of distribution algorithms, Why almost all \(k\)-colorable graphs are easy to color, Optimal testing for planted satisfiability problems, Unnamed Item, Unnamed Item, Satisfiability threshold for random regular \textsc{nae-sat}, A rigorous analysis of the cavity equations for the minimum spanning tree, On the survey-propagation equations in random constraint satisfiability problems, Propagation of external regulation and asynchronous dynamics in random Boolean networks, The random fractional matching problem, The network source location problem: ground state energy, entropy and effects of freezing, The theoretical capacity of the Parity Source Coder, Threshold values of random K‐SAT from the cavity method, Statistical and algebraic analysis of a family of random Boolean equations, Pruning processes and a new characterization of convex geometries, $$P\mathop{ =}\limits^{?}NP$$, A New Approach to Laplacian Solvers and Flow Problems, Rigid Colorings of Hypergraphs and Contiguity, The Boolean satisfiability problem in Clifford algebra, The number of solutions for random regular NAE-SAT, Gallager error-correcting codes for binary asymmetric channels, Unnamed Item, A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold, Streamlining variational inference for constraint satisfaction problems, Approximate survey propagation for statistical inference, Biased landscapes for random constraint satisfaction problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Generalized approximate survey propagation for high-dimensional estimation *, Belief propagation: accurate marginals or accurate partition function—where is the difference?, Coordination problems on networks revisited: statics and dynamics, Unnamed Item, Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length, Leveraging GPUs for effective clause sharing in parallel SAT solving
Uses Software
Cites Work
