Is SP BP?
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
77 page double-spaced single-column submitted version to IEEE Transactions on Information Theory
77 page double-spaced single-column submitted version to IEEE Transactions on Information Theory