Statistical physics of random constraint satisfaction problems

Riccardo Zecchina

We will provide a brief review on some recent advances in the
statistical mechanics analysis of randomized constraint satisfaction
problems -- such as graph coloring, satisfiability and parity check
equations -- and on a related class of message-passing algorithms
-- the Survey Propagation (SP) algorithms -- that are able to deal
efficiently with the clustering of solutions.

Connections with information theory will be displayed in some detail 
together with a  short review of mathematical open problems.
Some time will be also dedicated to the discussion of perspectives and 
potential  applications.

Exercises and reading material will be given prior to the lectures.