Survey-propagation decimation through distributed local computations

Details Survey-propagation decimation through distributed local computations Survey-propagation decimation through distributed local computations

2005-11-30

arxiv.org/abs/cond-mat/0512002v1

J. Stat. Mech. (2005) P11016

Physics

Condensed Matter

Disordered Systems and Neural Networks

18 pages, 10 figures

Scientific paper

10.1088/1742-5468/2005/11/P11016

We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm. The first solver, called the "SP diffusion algorithm", diffuses as dynamical information the maximum bias over the system, so that variable nodes can decide to freeze in a self-organized way, each variable making its decision on the basis of purely local information. The second solver, called the "SP reinforcement algorithm", makes use of time-dependent external forcing messages on each variable, which let the variables get completely polarized in the direction of a solution at the end of a single convergence. Both methods allow us to find a solution of the random 3-SAT problem in a range of parameters comparable with the best previously described serialized solvers. The simulated time of convergence towards a solution (if these solvers were implemented on a distributed device) grows as log(N).

Affiliated with

Also associated with

No associations

Rating

Survey-propagation decimation through distributed local computations 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 decimation through distributed local computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Survey-propagation decimation through distributed local computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-90926