Some remarks on the survey decimation algorithm for K-satisfiability

In this note we study the convergence of the survey decimation algorithm. An analytic formula for the reduction of the complexity during the decimation is derived. The limit of the converge of the algorithm are estimated in the random case: interesting phenomena appear near the boundary of convergence.

• Publication year

  2003

• Venue

  arXiv.org

• Publication date

  2003-01-16

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  arXiv cs/0301015
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On local equilibrium equations for clustering states

  2002cited by this paper
• The Cavity Method at Zero Temperature

  2002cited by this paper
• Survey propagation: An algorithm for satisfiability

  2002cited by this paper
• On the survey-propagation equations for the random K-satisfiability problem

  2002cited by this paper
• Phase transitions in combinatorial problems

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

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

  2000cited by this paper
• Typical random 3-SAT formulae and the satisfiability threshold

  2000cited by this paper
• Generalized Belief Propagation

  2000cited by this paper
• Entropy of the K-satisfiability problem.

  1996cited by this paper
• Critical Behavior in the Satisfiability of Random Boolean Expressions

  1994cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper

• Efficient solution of Boolean satisfiability problems with digital memcomputing

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

  2015influential citation
• On Sparse Discretization for Graphical Games

  2014cites this paper
• Spin Glasses, Boolean Satisfiability, and Survey Propagation

  2013cites this paper
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction

  2011cites this paper
• Statistical Physics of Hard Optimization Problems

  2008cites this paper
• Random Subcubes as a Toy Model for Constraint Satisfaction Problems

  2007cites this paper
• N ov 2 00 5 Survey-propagation decimation through distributed local computations

  2007cites this paper
• On the solution-space geometry of random constraint satisfaction problems

  2006cites this paper
• Statistical mechanics of optimization problems

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

  2005cites this paper
• Statistical physics, optimization and source coding

  2005cites this paper
• Minimizing energy below the glass thresholds.

  2004cites this paper
• On the Probabilistic Approach to the Random Satisfiability Problem

  2003cites this paper
• Constraint Optimization and Statistical Mechanics

  2003cites this paper
• Approximate analysis of search algorithms with "physical" methods

  2003cites this paper