Talks
Fall 2020

Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model

Tuesday, Jan. 11, 2022 9:30 am10:20 am PST

Add to Calendar

Speaker: 

Ahmed El Alaoui (Cornell University)

Location: 

Calvin Lab Auditorium

We propose an algorithm which efficiently samples from the SK measure with no external field at all inverse temperatures beta < 1/2.  The approach uses a discretized version of the Stochastic Localization (SL) process of Eldan (2013), and the analysis relies on a comparison with a planted model combined with a new information-theoretic interpretation of the SL process. We believe this algorithm should succeed for all beta<1. Finally, we show that due to disorder chaos, 'stable' algorithms cannot approximately sample from the SK measure for beta>1. This result, which pertains to sampling, parallels the use of the overlap gap property to show algorithmic impossibility results for random optimization problems.
This is a joint work with Andrea Montanari and Mark Sellke.