On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
arXiv:0904.3395 · doi:10.1088/1742-5468/2009/09/P09001
Abstract
We introduce a version of the cavity method for diluted mean-field spin models that allows the computation of thermodynamic quantities similar to the Franz-Parisi quenched potential in sparse random graph models. This method is developed in the particular case of partially decimated random constraint satisfaction problems. This allows to develop a theoretical understanding of a class of algorithms for solving constraint satisfaction problems, in which elementary degrees of freedom are sequentially assigned according to the results of a message passing procedure (belief-propagation). We confront this theoretical analysis to the results of extensive numerical simulations.
arXiv comment32 pages, 24 figures
References in corpus (20)
- The Bethe lattice spin glass revisited
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Phase Transitions in the Coloring of Random Graphs
- Recipes for metastable states in Spin Glasses
- Statistical mechanics of the random K-SAT model
- Reconstruction on trees and spin glass transition
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- A variational description of the ground state structure in random satisfiability problems
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Focused Local Search for Random 3-Satisfiability
- How to Compute Loop Corrections to Bethe Approximation
- Survey-propagation decimation through distributed local computations
- Relaxation and Metastability in the RandomWalkSAT search procedure
- Constraint satisfaction problems with isolated solutions are hard
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
- Complexity transitions in global algorithms for sparse linear systems over finite fields
- Criticality and Universality in the Unit-Propagation Search Rule
- Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
Cited by in corpus (31)
- Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
- The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
- Generalization of the cavity method for adiabatic evolution of Gibbs states
- The backtracking survey propagation algorithm for solving random K-SAT problems
- Phase transitions in semisupervised clustering of sparse networks
- Random Pinning Glass Transition: Hallmarks, Mean-Field Theory and Renormalization Group Analysis
- Minimal contagious sets in random regular graphs
- The condensation phase transition in random graph coloring
- Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
- Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
- Biased landscapes for random Constraint Satisfaction Problems
- Glassy Critical Points and Random Field Ising Model
- Random-Field Ising like effective theory of the glass transition: I Mean-Field Models
- A general approach to systems with randomly pinned particles: unfolding and clarifying the Random Pinning Glass Transition
- The large deviations of the whitening process in random constraint satisfaction problems
- Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
- Stochastic optimization by message passing
- Inference of the sparse kinetic Ising model using the decimation method
- Aging and relaxation near Random Pinning Glass Transitions
- A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
- The decimation process in random k-SAT
- Susceptibility Propagation for Constraint Satisfaction Problems
- Typical Approximation Performance for Maximum Coverage Problem
- Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
- The solution space structure of planted constraint satisfaction problems with growing domains
- Correcting beliefs in the mean-field and Bethe approximations using linear response
- Decimation flows in constraint satisfaction problems
- Algorithmic thresholds in combinatorial optimization depend on the time scaling
- Searching for feasible stationary states in reaction networks by solving a Boolean constraint satisfaction problem
- The closest vector problem and the zero-temperature p-spin landscape for lossy compression
- Interacting Copies of Random Constraint Satisfaction Problems