Computer Science/Discrete Mathematics Seminar I

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.