Seminars & Events

Computations In Science Seminar
"Spin Glasses in Applied Mathematics"

DATE: December 5, 2007
TIME: 12:30 p.m.
SPEAKER: Scott Kirkpatrick
LOCATION: KPTC 206, University of Chicago

Description:
Prior to the mid-1970s, optimization research centered on effective search within irregular, sometimes nonlinear attractor basins with a single minimum. Conjugate gradient methods, for example, were developed in that framework. The study of spin glasses and Monte Carlo simulation brought a realization that most interesting problems have multiple minima, and most engineering applications are satisfied with
any minimum that satisfies certain objectives. A second contribution was the realization that phase transitions in disordered systems have consequences for the cost of search in typical (but not worst-case) conditions. Recent methods, such as message-passing solutions to cavity mean-field descriptions of combinatoric problems have brought at least a thousand-fold increase in the size of typically hard problems which are now numerically tractable. But now such methods are being used as Shannon-optimal decoders, in a situation in which only one solution, the correct decoding, is of interest. Provably correct methods such as linear and semidefinite programming may also apply. We have been studying combinatoric problems lying right at the boundary
between convex and harder optimization, such as Sudoku.

More Information:
If you Would like to meet with the speaker or join us for a meal, please contact Arnab Banerjee abjee@uchicago.edu.
(Discussion over bag-lunch at 12:15 p.m.)
Save the event to your calendar [schedule.ics]