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.