|Stochastic Systems Group|
Mixing and Clustering in Message-Passing Schemes
The belief propagation algorithm and its variants have recently been shown to work quite well on hard constraint satisfaction problems. Survey propagation is one such algorithm that has been developed for solving the k-SAT problem. This algorithm is based on two hypotheses deriving from the replica symmetry breaking theory developed for the statistical mechanics of spin glasses. The first is that the solutions of constraint satisfaction problems near threshold organize into disjoint clusters. The second is that within each cluster there is spatial mixing. In this talk we show that both hypotheses hold for a large class of constraint satisfaction problems.
Problems with this site should be emailed to email@example.com