A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a \((1 \pm \varepsilon)\) cut (or spectral) sparsifier which preserves only \(O(n/\varepsilon^2)\) reweighted edges. However, when applying this result to Cayley graphs, the resulting sparsifier is no longer necessarily a Cayley graph — it can be an arbitrary subset of edges.

Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statistical inference. In the mean-field setting, we design deterministic quasipolynomial-time algorithms for estimating the partition function to arbitrarily high accuracy for all inverse temperatures in the second moment regime. In particular, for the Sherrington--Kirkpatrick model, our algorithms succeed for the entire replica-symmetric phase. To achieve this, we study the locations of the zeros of the partition function. Notably, our methods are conceptually simple, and apply equally well to the spherical case and the case of Ising spins.