###
Glassy phase transitions in hard computer science problems

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.