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

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 us 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 with the results of extensive numerical simulations.

• Publication year

  2009

• Venue

  arXiv.org

• Publication date

  2009-04-22

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1088/1742-5468/2009/09/P09001arXiv 0904.3395
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Information, Physics, and Computation

  2009cited by this paper
• Clusters of solutions and replica symmetry breaking in random k-satisfiability

  2008cited by this paper
• Constraint satisfaction problems with isolated solutions are hard

  2008cited by this paper
• Proceedings of the International Conference on Analysis of Algorithms

  2007cited by this paper
• Phase Transitions in the Coloring of Random Graphs

  2007cited by this paper
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions

  2007cited by this paper
• Gibbs states and the set of solutions of random constraint satisfaction problems

  2006cited by this paper
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios

  2006cited by this paper
• Survey-propagation decimation through distributed local computations

  2005cited by this paper
• Focused local search for random 3-satisfiability

  2005cited by this paper
• A message-passing algorithm with damping

  2005cited by this paper
• Reconstruction on Trees and Spin Glass Transition

  2005cited by this paper
• Criticality and universality in the unit-propagation search rule

  2005cited by this paper
• Maxwell Construction: The Hidden Bridge Between Iterative and Maximum a Posteriori Decoding

  2005cited by this paper
• How to compute loop corrections to the Bethe approximation

  2005cited by this paper
• A new look at survey propagation and its generalizations

  2004cited by this paper
• THE THRESHOLD FOR RANDOM k-SAT IS 2 log 2−O(k)

  2004cited by this paper
• Spin Glasses: A Challenge for Mathematicians

  2003cited by this paper
• about the Internet and Networking : 2010 – 2019

  2003cited by this paper
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms

  2003cited by this paper
• Relaxation and metastability in a local search procedure for the random satisfiability problem.

  2003cited by this paper
• Two Solutions to Diluted p-Spin Models and XORSAT Problems

  2003cited by this paper
• Spin glasses : a challenge for mathematicians : cavity and mean field models

  2003cited by this paper
• CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Complexity transitions in global algorithms for sparse linear systems over finite fields

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices.

  2002cited by this paper
• Lower bounds for random 3-SAT via differential equations

  2001cited by this paper
• Information

  2001cited by this paper
• Results related to threshold phenomena research in satisfiability: lower bounds

  2001cited by this paper
• Factor graphs and the sum-product algorithm

  2001cited by this paper
• Upper bounds on the satisfiability threshold

  2001cited by this paper
• THE EUROPEAN PHYSICAL JOURNAL B c○ EDP Sciences

  2000cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• IEEE TRANSACTIONS ON INFORMATION THEORY

  1998cited by this paper
• In Advances in Neural Information Processing Systems

  1996cited by this paper
• Analysis of Two Simple Heuristics on a Random Instance of k-SAT

  1996cited by this paper
• Recipes for metastable states in spin glasses

  1995cited by this paper
• Algorithms

  1992cited by this paper
• Neural Computation

  1989cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Solutions of ordinary differential equations as limits of pure jump markov processes

  1970cited by this paper
• A Computing Procedure for Quantification Theory

  1960cited by this paper

• Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

  2026cites this paper
• Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms

  2025cites this paper
• Beyond-mean-field fluctuations for the solution of constraint satisfaction problems

  2025cites this paper
• Xenophobia based on a few attributes can impede society's cohesiveness

  2025cites this paper
• Interacting copies of random-constraint satisfaction problems.

  2025cites this paper
• Belief Propagation Guided Decimation on Random k-XORSAT

  2025influential citation
• Algorithmic thresholds in combinatorial optimization depend on the time scaling

  2025cites this paper
• Computational bottlenecks for denoising diffusions

  2025cites this paper
• Optimization of random cost functions and statistical physics

  2024cites this paper
• Limits of Sequential Local Algorithms on the Random k-XORSAT Problem

  2024cites this paper
• Sampling from mean-field Gibbs measures via diffusion processes

  2023cites this paper
• Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective

  2023influential citation
• Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

  2022cites this paper
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression

  2022cites this paper
• The cavity method: from exact solutions to algorithms

  2022cites this paper
• Equivalence of state equations from different methods in high-dimensional regression

  2022cites this paper
• The high- d landscapes paradigm: spin-glasses, and beyond

  2022cites this paper
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains

  2021cites this paper
• The solution space structure of planted constraint satisfaction problems with growing domains

  2021cites this paper
• The overlap gap property: A topological barrier to optimizing over random structures

  2021cites this paper
• Clustering phase of a general constraint satisfaction problem model d-k-CSP

  2020cites this paper
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness

  2019influential citation
• Boolean constraint satisfaction problems for reaction networks

  2019influential citation
• DECIMAXSUM: Using Decimation to Improve Max-Sum on Cyclic DCOPs

  2018cites this paper
• Random-field Ising-like effective theory of the glass transition. I. Mean-field models

  2018cites this paper
• Biased landscapes for random constraint satisfaction problems

  2018influential citation
• Typical Approximation Performance for Maximum Coverage Problem

  2017cites this paper
• Belief Propagation Guided Decimation Fails on Random Formulas

  2017cites this paper
• Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem

  2017cites this paper
• Analysing Survey Propagation Guided Decimation on Random Formulas

  2016cites this paper
• Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes

  2016cites this paper
• The large deviations of the whitening process in random constraint satisfaction problems

  2016cites this paper
• Message Passing and Combinatorial Optimization

  2015cites this paper
• Inference of the sparse kinetic Ising model using the decimation method.

  2015cites this paper
• The Condensation Phase Transition in Random Graph Coloring

  2015cites this paper
• The backtracking survey propagation algorithm for solving random K-SAT problems

  2015cites this paper
• ON THE SPINE OF 3-XORSAT

  2015influential citation
• A statistical physics approach to different problems in network theory

  2015cites this paper
• The condensation phase transition in the regular k-SAT model

  2015cites this paper
• S tructure vs C ombinatorics in C omputational C omplexity

  2014cites this paper
• Structure vs Combinatorics in Computational Complexity

  2014cites this paper
• Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem

  2014cites this paper
• Perturbed message passing for constraint satisfaction problems

  2014cites this paper
• Identifying All Moiety Conservation Laws in Genome-Scale Metabolic Networks

  2014cites this paper
• The Condensation Phase Transition in Random Graph Coloring

  2014cites this paper
• Aspects of Statistical Physics in Computational Complexity

  2014influential citation
• The Cavity Method in Coding Theory

  2014cites this paper
• Minimal Contagious Sets in Random Regular Graphs

  2014cites this paper
• Minimal Contagious Sets in Random Regular Graphs

  2014cites this paper
• Polarization and Spatial Coupling - Two Techniques to Boost Performance

  2013cites this paper
• Boolean constraint satisfaction problems for reaction networks

  2013cites this paper
• Mean-field disordered systems : glasses and optimization problems, classical and quantum

  2013influential citation
• Correcting beliefs in the mean-field and Bethe approximations using linear response

  2013cites this paper
• Searching for feasible stationary states in reaction networks by solving a Boolean constraint satisfaction problem.

  2013cites this paper
• The asymptotic k-SAT threshold

  2013cites this paper
• Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation

  2013cites this paper
• Approaching the rate-distortion limit by spatial coupling with belief propagation and decimation

  2013cites this paper
• Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains.

  2012cites this paper
• Random pinning glass transition: hallmarks, mean-field theory and renormalization group analysis.

  2012cites this paper
• Reweighted Belief Propagation and Quiet Planting for Random K-SAT

  2012cites this paper
• The Network Source Location Problem: Ground State Energy, Entropy and Effects of Freezing

  2012cites this paper
• The Decimation Process in Random k-SAT

  2011influential citation
• Ideal glass transitions by random pinning

  2011cites this paper
• Characterizing and improving generalized belief propagation algorithms on the 2D Edwards–Anderson model

  2011cites this paper
• A message-passing approach to random constraint satisfaction problems with growing domains

  2011cites this paper
• Complexity of Bethe Approximation

  2011cites this paper
• The Complexity of Approximating a Bethe Equilibrium

  2011cites this paper
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems

  2011cites this paper
• Aging and relaxation near random pinning glass transitions

  2011cites this paper
• Inference algorithm for finite-dimensional spin glasses: belief propagation on the dual lattice.

  2011cites this paper
• Stochastic optimization by message passing

  2011cites this paper
• On belief propagation guided decimation for random k-SAT

  2010influential citation
• Correlation-based decimation in constraint satisfaction problems

  2010cites this paper
• Decimation flows in constraint satisfaction problems

  2009cites this paper
• POLITECNICO DI TORINO Repository ISTITUZIONALE Unreasonable effectiveness of learning neural networks : From accessible states and robust ensembles to basic algorithmic schemes

  year unknowncites this paper