Andrea Montanari - Stanford University
Wednesday, August 24th, 10:45AM (Zoom meeting starts at 10:30)
“Algorithmic spin glass theory”
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.]