 |
Center for Nonlinear Studies |
Message passing algorithms such as Belief Propagation (BP) are widely used for probabilistic inference in graphical models. BP has been successfully applied to computational problems in rather diverse fields, such as computer vision, information theory, and statistical mechanics. Recently, the application of BP has also been explored for solving hard instances of constraint satisfaction problems, for example Boolean Satisfiability (SAT) and Graph Coloring (COL). Direct application of BP, unfortunately, runs into problems with convergence and accuracy, due to the spatial distribution of solutions in the search space, in particular, when solutions are organized in a large number of \"clusters\" comprised of \"similar\" solutions. To overcome these difficulties, a new technique, called Survey Propagation (SP), has been introduced in the physics community. SP reasons about solution clusters of the underlying problem rather than about individual solutions, and can solve hard random instances of combinatorial problems with millions of variables. This surprising observation initiated an intensive research effort of broadening the applicability of similar algorithms.
In this talk, I will introduce a framework of reasoning about solution clusters in a purely combinatorial way. Within this framework, the original SP algorithm for SAT can be derived as an instance of BP, and new algorithms developed for approximately counting solution clusters in other CSPs. At the same time, the framework allows one to prove certain interesting properties of clusters that give further insights into the geometry of solution spaces. Part of this work will be presented at the NIPS\'08 conference.
This is joint work with Ashish Sabharwal and Bart Selman at Cornell University
Host: Shiva Kasiviswanathan