Seminars & Colloquia Calendar

Abstract: Mean field spin glasses are high-dimensional random functions with special exchangeability properties. These models were originally motivated by the study of disordered magnetic materials. However, it soon become clear that a large number of random optimization problems of interest in computer science and statistics fit this framework. Parisi's replica symmetry breaking (RSB) theory allows to determine the asymptotics of the optimal value of these problems. Can RSB shed light on relevant algorithmic questions as well?
Here is a specific formalization of this question: Is there a polynomial time algorithm that outputs a feasible solution of these optimization problems whose value is, with high probability, within a factor rho of the optimum?
I will survey recent rigorous work that points at a remarkably precise answer for
this question. Time permitting, I will talk about the problem of sampling from the Sherrington-Kirkpatrick
Boltzmann measure.
[Based on joint work with Ahmend El Alaoui and Mark Sellke.]