From: Riccardo Zecchina <>
Newsgroups: milano.seminari
Subject: 17-06-2004 Statistical physics, Optimization and Coding Theory
Date: Fri, 11 Jun 2004 12:37:38 +0000 (UTC)

                               Seminario Teorico

                              Il giorno 17-06-2004
                        alle ore 15:00 in Aula Consiglio

                               Riccardo Zecchina

                        terra' un seminario dal titolo:

              Statistical physics, Optimization and Coding Theory

 The combinatorial problem of satisfying a given set of constraints that depend
on N discrete variables is a fundamental one in optimization and coding theory.
  Even for randomly generated problem instances, the question "does it exist a
variable assignment that satisfies all constraints?" may become extraordinarily
 difficult to solve in some range of parameters where a glass phase sets in. We
shall provide a brief review on the recent advances in the statistical mechanics
approach to these satisfiability problems and show how the analytic results help
     in the design a new class of message-passing algorithms -- the Survey
     Propagation (SP) algorithms -- that are able to solve efficiently some
  combinatorial problems considered intractable. Applications to biologically
  motivated problems and to coding theory will be described. Open problems and
                       perspectives will be given in the