Schedule Apr 16, 2003
Glass Phases in Optimization Problems
Dr. Marc Mézard, CNRS - Université Paris Sud
http://ipnli5.in2p3.fr/~lptms/membres/mezard/
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)

[00] [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24]

Author entry (protected)