Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Mixing and Clustering in Message-Passing Schemes

Sekhar Tatikonda
Yale University

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