The Sherrington-Kirkpatrick measure is a random probability distribution on the hypercube, which is a central object of study in probability theory and in the mean-field theory of disordered statistical physics models.  

In this talk I will present an algorithm which efficiently samples from the SK measure with no external field and at high temperature. The approach uses a discretized version of the stochastic localization process of Eldan, together with a subroutine for computing the mean vector, or magnetization, of a family of SK measures tilted by an appropriate external field. This approach is very general and has wide applicability.  

Our analysis shows that the algorithm outputs an approximate sample (in a certain weak sense) from the the SK measure, for all inverse temperatures beta < 1/2. In a recent paper, Celentano (2022) shows that our algorithm succeeds up to the critical temperature beta < beta_c = 1.  

Conversely, we show that in the ‘low temperature’ phase beta >1, no ‘stable’ algorithm can approximately sample from the SK measure. This exploits a newly established strong version of a property called `disorder chaos’ exhibited by SK in this regime. 

The above two results settle the question of the computational tractability of sampling from SK for all temperatures except the critical one.     

This is based on a joint work with Andrea Montanari and Mark Sellke.