Survey Propagation as local equilibrium equations

Details Survey Propagation as local equilibrium equations Survey Propagation as local equilibrium equations

2003-12-18

arxiv.org/abs/cond-mat/0312483v5

J. Stat. Mech., P06007 (2004)

Physics

Condensed Matter

Disordered Systems and Neural Networks

13 pages, 3 figures

Scientific paper

10.1088/1742-5468/2004/06/P06007

It has been shown experimentally that a decimation algorithm based on Survey Propagation (SP) equations allows to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum-product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value -- $*$ -- when they are not forced by the combinatorial constraints. An appropriate ``local equilibrium condition'' cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by SP. These results may help to clarify the geometrical notion of clusters assumed by SP for the random K-SAT or random graph coloring (where it is conjectured to be exact) and helps to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact.

Affiliated with

Also associated with

No associations

Rating

Survey Propagation as local equilibrium equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Survey Propagation as local equilibrium equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Survey Propagation as local equilibrium equations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-307838