Phase Transitions in Optimization Problems

Marc Mézard, Université Paris Sud, CNRS

Given a large set of discrete variables, and some constraints between them, is there a way to choose the variables so that all constraints will be satisfied? This "satisfiability" problem is one of the most fundamental complex optimization problems. It turns out to be particularly difficult in some range of parameters where a phase transition to a glass phase takes place. Taking satisfiability as an example, this talk will give an introduction to the statistical physics of optimization problems and their phase diagrams. It will discuss in particular the emergence of glass phases, how they are responsible for a dramatic slowdown of algorithms, and how analytic insight into this glassy nature can help to design new types of algorithms which solve very large constraint satisfaction problems.

The P/T Colloquium is
typically held each
Thursday, 3:45–5:00 PM.
Refreshments are served
at 3:15 PM.