Survey propagation: An algorithm for satisfiability
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1113992
- Theory and Applications of Satisfiability Testing
- A heuristic survey propagation algorithm for solving QBF problems
- A new algorithm for the propositional satisfiability problem
- On the survey-propagation equations in random constraint satisfiability problems
- Characterizing Propagation Methods for Boolean Satisfiability
- scientific article; zbMATH DE number 1206044
- A Computational Study of Satisfiability Algorithms for Propositional Logic
- Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
- scientific article; zbMATH DE number 4039349
Cites work
- Gibbs measures and phase transitions
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- scientific article; zbMATH DE number 1113991 (Why is no real title available?)
- scientific article; zbMATH DE number 1947423 (Why is no real title available?)
- scientific article; zbMATH DE number 3251924 (Why is no real title available?)
Cited in
(95)- Pruning processes and a new characterization of convex geometries
- Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
- Threshold saturation in spatially coupled constraint satisfaction problems
- A review of message passing algorithms in estimation of distribution algorithms
- The number of solutions for random regular NAE-SAT
- 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
- Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
- Proof of the satisfiability conjecture for large \(k\)
- Leveraging cluster backbones for improving MAP inference in statistical relational models
- Optimal testing for planted satisfiability problems
- The Boolean satisfiability problem in Clifford algebra
- Maximum independent sets on random regular graphs
- Understanding science through the computational lens
- Pairs of SAT-assignments in random Boolean formulæ
- The asymptotics of the clustering transition for random constraint satisfaction problems
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Satisfiability thresholds beyond k-XORSAT
- A new look at survey propagation and its generalizations
- Performance of sequential local algorithms for the random NAE-K-SAT problem
- The decimation process in random k-SAT
- Survey propagation as local equilibrium equations
- Complete convergence of message passing algorithms for some satisfiability problems
- Statistical mechanics of complex neural systems and high dimensional data
- 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
- Statistical physics and network optimization problems
- Random instances of problems in NP -- algorithms and statistical physics
- scientific article; zbMATH DE number 5287580 (Why is no real title available?)
- A new look at survey propagation and its generalizations
- A spectral approach to analysing belief propagation for 3-colouring
- Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
- 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
- Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
- The consequences of eliminating NP solutions
- Tropical limit and a micro-macro correspondence in statistical physics
- Analysing survey propagation guided decimationon random formulas
- A new approach to Laplacian solvers and flow problems
- scientific article; zbMATH DE number 2159024 (Why is no real title available?)
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- An algebraic hardness criterion for surjective constraint satisfaction.
- Investigation of commuting Hamiltonian in quantum Markov network
- Local search for Boolean satisfiability with configuration checking and subscore
- The random fractional matching problem
- The theoretical capacity of the parity source coder
- Approximate survey propagation for statistical inference
- Biased landscapes for random constraint satisfaction problems
- Disordered systems insights on computational hardness
- The solution space structure of planted constraint satisfaction problems with growing domains
- Satisfiability thresholds for regular occupation problems
- scientific article; zbMATH DE number 7564631 (Why is no real title available?)
- Generating weighted MAX-2-SAT instances with frustrated loops: an RBM case study
- Statistical and algebraic analysis of a family of random Boolean equations
- Rigid colorings of hypergraphs and contiguity
- Gallager error-correcting codes for binary asymmetric channels
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- On the interpolation between product-based message passing heuristics for SAT
- Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
- Convergence of warning propagation algorithms for random satisfiable instances
- Spanning trees in random satisfiability problems
- Threshold values of random K‐SAT from the cavity method
- A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold
- A Computing Procedure for Quantification Theory
- Theory and Applications of Satisfiability Testing
- A simple algorithm for random colouring G(n, d/n) using (2 + )d colours
- Perturbed message passing for constraint satisfaction problems
- Characterizing Propagation Methods for Boolean Satisfiability
- Streamlining variational inference for 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
- Satisfiability threshold for power law random 2-SAT in configuration model
- Satisfiability threshold for random regular \textsc{nae-sat}
- Why adiabatic quantum annealing is unlikely to yield speed-up
- On the thresholds in linear and nonlinear Boolean equations
- Message-passing algorithms for inference and optimization
- Reduction-based MAX-3SAT with low nonlinearity and lattices under recombination
- Searching for (sharp) thresholds in random structures: where are we now?
- Limits of sequential local algorithms on the random k-XORSAT problem
- Satisfiability thresholds for regular occupation problems
- Bounded degree nonnegative counting CSP
- Belief propagation guided decimation on random k-XORSAT
- The network source location problem: ground state energy, entropy and effects of freezing
- A comparative runtime analysis of heuristic algorithms for satisfiability problems
- A collaborative approach for multi-threaded SAT solving
- The asymptotic k-SAT threshold
- Why almost all k-colorable graphs are easy to color
This page was built for publication: Survey propagation: An algorithm for satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5318246)
