New Iterative Algorithms for Hard Combinatorial Problems
Riccardo Zecchina · 2004
This chapter contains sections titled: Introduction Combinatorial Decision Problems, K-SAT and the Factor Graph Representation Random K-SAT Growth Process Algorithm: Probabilities, Messages and Their Statistics Traditional Message-passing Algorithm: Belief Propagation as Simple Cavity Equations Survey Propagation Equations Decimating Variables According to Their Statistical Bias Conclusions and Perspectives References