From: Riccardo Zecchina <troubles@fisica.unimi.it> 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 ICTP-Trieste terra' un seminario dal titolo: Statistical physics, Optimization and Coding Theory Abstract: 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