Is SP BP?

Details Is SP BP? Is SP BP?

2008-01-29

arxiv.org/abs/0801.4571v1

Computer Science

Information Theory

77 page double-spaced single-column submitted version to IEEE Transactions on Information Theory

Scientific paper

The Survey Propagation (SP) algorithm for solving $k$-SAT problems has been shown recently as an instance of the Belief Propagation (BP) algorithm. In this paper, we show that for general constraint-satisfaction problems, SP may not be reducible from BP. We also establish the conditions under which such a reduction is possible. Along our development, we present a unification of the existing SP algorithms in terms of a probabilistically interpretable iterative procedure -- weighted Probabilistic Token Passing.

Affiliated with

Also associated with

No associations

Rating

Is SP BP? 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 Is SP BP?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Is SP BP? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-121111