Is SP BP?
| dc.creator | Tu, Ronghui | |
| dc.creator | Mao, Yongyi | |
| dc.creator | Zhao, Jiying | |
| dc.date | 2008-01-29 | |
| dc.date.accessioned | 2026-07-07T08:57:15Z | |
| dc.date.available | 2026-07-07T08:57:15Z | |
| dc.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. | |
| dc.description | 77 page double-spaced single-column submitted version to IEEE Transactions on Information Theory | |
| dc.identifier | https://arxiv.org/abs/0801.4571 | |
| dc.identifier | http://arxiv.org/abs/0801.4571 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/146892 | |
| dc.subject | Information Theory | |
| dc.title | Is SP BP? | |
| dc.type | text |