Apr 16, 2003
Glass Phases in Optimization Problems
Dr. Marc Mézard, CNRS - Université Paris Sud
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, the
appearance 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.
Audio requires RealPlayer by RealNetworks.
Begin WebCam and audio for the whole talk: high bandwidth or medium bandwidth.
Or, begin audio only for the whole talk:
high bandwidth or low bandwidth.
(Or, right-click to download the whole audio file.)
To begin viewing slides, click on the first slide below.
(Or, view as pdf. Or, view as ps)
Author entry (protected)