On zeros and algorithms for disordered systems

Counting and sampling are fundamental algorithmic primitives in high-dimensional statistics and computer science. For many models, there is an enormous literature studying the worst-case computational complexity of these tasks and how they connect to phase transitions the underlying system undergoes as its parameters (e.g., "temperature") are varied. Their average-case complexity is comparatively far less understood.

 

We study "mean-field spin glasses", fundamental probability distributions originating in statistical physics which form a useful playground for new algorithms and mathematical techniques. For the Sherrington-Kirkpatrick model, we design the first quasipolynomial-time algorithm to estimate its partition function to arbitrarily high accuracy all the way up to the "replica-symmetric threshold", a natural phase transition believed to delineate between computationally tractable and intractable regimes. To achieve this, we study the locations of the zeros of the partition function, taking inspiration from the seminal Lee-Yang program.