TIME: 1:30-2:20 pm,  December 11, 2007

PLACE: CSE 503  

SPEAKER: Riccardo Zecchina
         Politecnico di Torino

TITLE: Survey and Belief Propagation algorithms 
       for constraint satisfaction problems

ABSTRACT:
Survey and Belief Propagation are probabilistic message passing
algorithms which can be  very efficient in solving random constraint
satisfaction problems (e.g. random K-sat, graph coloring and many
others).  In this talk we will give a brief review of the geometrical 
facts which are at the base of the design of such algorithms and discuss 
the relevance of some large deviation phenomena.
We will end the talk by describing preliminary results concerning the
application of similar techniques to problems with non-local
constraints, like  TSP or Steiner trees on random graphs.