Seminars & Colloquia Calendar

Download as iCal file

Mathematical Physics Seminar

Algorithmic spin glass theory

Andrea Montanari - Stanford University

Location:  Zoom
Date & time: Wednesday, 24 August 2022 at 10:45AM - 11:45AM

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.]

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.