![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/geometry_and_computation_in_high_dimensions.png?itok=c5SxhQMm)
Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model
Ahmed El Alaoui (Cornell University)
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.