Marc Mezard, University of Paris Sud, Orsay
A new research area is developing rapidly at the crossroads between statistical physics, information theory, and combinatorial optimization. It studies networks of many discrete variables interacting through local constraints. Examples range from spin glasses to error correcting codes, graph coloring or the satisfiability of Boolean formulas.
In all these problems one observes phase transitions at some critical values of the density of constraints. Some of these transitions correspond to the appearance of glassy phases bearing strong similarities to those studied in the last decades in structural glasses.
This talk will survey the existence and importance of glassy phases in various areas of computer science and information theory, with a particular focus on the basic problem of satisfiability. It will describe the important recent theoretical and algorithmic progress in this field using statistical physics concepts and methods.