On local equilibrium equations for clustering states

Abstract

In this note we show that local equilibrium equations (the generalization of the TAP equations or of the belief propagation equations) do have solutions in the colorable phase of the coloring problem. The same results extend to other optimization problems where the solutions has cost zero (e.g. K-satisfiability). On a random graph the solutions of the local equilibrium equations are associated to clusters of configurations (clustering states). On a random graph the local equilibrium equations have solutions almost everywhere in the uncolored phase; in this case we have to introduce the concept quasi-solution of the local equilibrium equations.

9 pages

Cited by in corpus (11)

• Survey Propagation as local equilibrium equations
• Focused Local Search for Random 3-Satisfiability
• Inducing Effect on the Percolation Transition in Complex Networks
• Circumspect descent prevails in solving random constraint satisfaction problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• The large deviations of the whitening process in random constraint satisfaction problems
• A New Look at Survey Propagation and its Generalizations
• Realizing interdependent couplings as thermal or higher-order interactions
• The number of solutions for random regular NAE-SAT
• Statistical mechanics of optimization problems