arXiv preprint ·
Color Coding for the Sherrington-Kirkpatrick Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a polynomial-time algorithm for approximating the partition function of mean-field mixed $p$-spin models to arbitrarily high accuracy throughout the second-moment regime. This improves the quasipolynomial-time algorithm of Bencs, Huang, Lee, Liu, and Regts (arXiv:2507.15616) and answers their open question. In particular, our result covers the entire replica-symmetric regime of the Sherrington--Kirkpatrick model. The algorithm is deterministic, runs in time polynomial in $n$ and $1/\varepsilon$, and succeeds for every typical realization of the disorder. Our main technical contribution is a new algorithmic application of color coding to the classical high-temperature expansion introduced by Aizenman, Lebowitz, and Ruelle in their study of fluctuations of the Sherrington--Kirkpatrick partition function. We combine this approach with the zero-freeness established by Bencs et al. (arXiv:2507.15616) to convert additive approximations into multiplicative ones.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Geometry of Lee-Yang Tensors
Mutually unbiased bases: common states, completion, and extension obstructions
The Differential Structure of Generators of KMS-Symmetric Quantum Markov Semigroups
Multipartite entanglement spreads
Spacetime Quasicrystals and Computational Complexity Theory in the Road Towards Quantum Gravity
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.