Computer Science/Discrete Mathematics Seminar I

Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model

Sampling from high-dimensional, multimodal distributions is a computationally challenging and fundamental task.  This talk will focus on a family of random instances of such problems described by random quadratic potentials on the hypercube known as the Sherrington-Kirkpatrick model.  I will describe an approximate sampling algorithm for the high temperature regime as well as matching low-temperature hardness results stemming from disorder chaos.  Our algorithm uses stochastic localization, which progressively tilts the desired measure towards a single configuration, together with an approximate message passing algorithm that is used to approximate the mean of the tilted measure.  Based on joint work with Ahmed El Alaoui and Andrea Montanari.

Date & Time

November 28, 2022 | 11:15am – 12:15pm

Location

Simonyi Hall 101 and Remote Access

Speakers

Speaker Affiliation

Member, School of Mathematics