On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms

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.

32 pages, 24 figures

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Constraint satisfaction problems with isolated solutions are hard
• 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