MATH DEPARTMENT COLLOQUIUM Andrea Montanari, Stanford University Algorithmic spin glass theory Wednesday, Nov 02 Fine Hall 314 / 4:30 PM - 5:30 PM In-Person and Online Talk Zoom Link: [ https://princeton.zoom.us/j/97792754638?pwd=MGFNcU5tMzZGczc5N0hpSTB6Y0hEUT09 | https://princeton.zoom.us/j/97792754638?pwd=MGFNcU5tMzZGczc5N0hpSTB6Y0hEUT09 ] 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 became 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 AHMED EL ALAOUI AND MARK SELLKE.