Lune

STOC2026Top-tier venue

On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses

Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses cites Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on9

  1. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systemsAram W. Harrow, Saeed Mehraban, Mehdi SoleimanifarSTOC 2020 · 38 citations
  2. Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationAhmed El Alaoui, Andrea Montanari, Mark SellkeFOCS 2022 · 29 citations
  3. Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric PerceptronEmmanuel Abbe, Shuangping Li, Allan SlyFOCS 2021 · 27 citations
  4. Entropic independence: optimal mixing of down-up random walksNima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham et al.STOC 2022 · 21 citations
  5. Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin GlassesBrice Huang, Sidhanth Mohanty, Amit Rajaraman, David X. WuSTOC 2025 · 13 citations

Related papers

  1. Learning the Sherrington-Kirkpatrick Model Even at Low TemperatureGautam Chandrasekaran, Adam R. KlivansSTOC 2025 · 1 citation
  2. Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness RegionZongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric VigodaSODA 2022 · 11 citations
  3. Phase Transitions via Complex Extensions of Markov ChainsJingcheng Liu, Chunyang Wang, Yitong Yin, Yixiao YuSTOC 2025 · 6 citations
  4. A Unified Approach to Learning Ising Models: Beyond Independence and Bounded WidthJason Gaitonde, Elchanan MosselSTOC 2024 · 5 citations
  5. Zeros of ferromagnetic 2-spin systemsHeng Guo, Jingcheng Liu, Pinyan LuSODA 2020 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines