Marc Mezard, CNRS - Université Paris Sud-"Glassy phase transitions in hard computer science problems"

Thu, Oct 21, 2010, 4:30 pm to 6:00 pm
Given a large set of discrete variables, and some constraints between them, is there a way to choose the variables so that all constraints are satisfied?This "satisfiability" problem is one of the most fundamental complex optimization problems. It also has very concrete applications, for instance in computer chip testing or in error correcting codes. There exist deep connections between this fundamental problem in computer science and structural glasses. By increasing the density of constraints in random satisfiability, one meets a phase transition to a glass phase, associated with a structural change in the satisfiability problem at the origin of computational hardness. This talk will survey some of the recent progress, both conceptual and algorithmic, obtained in hard computer science problems using statistical physics concepts and methods.

McDonnell A02