CS Paper Radar

A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model

Dylan Herman, Shouvanik Chakrabarti, Junhyung Lyle Kim, Guneykan Ozgul

cs.DS cond-mat.stat-mechmath.OCmath.PRquant-ph ·submitted 2026-11-03 17:28 UTC · v1

Abstract

Montanari's incremental approximate message passing (IAMP) algorithm [FOCS 2019; SIAM J. Comput., 2025] and the zero-temperature formulation of El Alaoui, Montanari and Sellke (AMS) [Ann. Probab., 2021] find a $(1-\varepsilon)$ approximation to the maximum Sherrington-Kirkpatrick (SK) energy in $C(\varepsilon)N^2$ operations for fixed accuracy, with probability tending to one as $N\to\infty$, under their respective full-support and access-model assumptions. However, it was unknown whether this approximation could be achieved with work polynomial in both $N$ and $1/\varepsilon$, together with quantitative guarantees at finite dimension. Under the same assumptions as AMS, we introduce grouped IAMP with exact Gaussian query outputs (GEG-IAMP), which is the first SK approximation algorithm with total work polynomial in $N$ and $1/\varepsilon$ and a finite-size guarantee above a dimension threshold polynomial in $1/\varepsilon$ and $\log(1/α)$. More precisely, for every $α\in(0,1/2)$, it returns a $(1-\varepsilon)$ approximation with probability at least $1-α$ whenever $N\ge \mathsf{K}\varepsilon^{-2}\log^2(e/\varepsilon)\log(\mathsf{K}/α)$, using $O(N^2/\varepsilon)$ work and $O(N^2)$ storage. GEG-IAMP replaces the Onsager correction by Reeves's coupling construction [arXiv:2508.10782] and groups Euler-Maruyama steps into $O(1/\varepsilon)$ matrix-vector products. We also prove a relative guarantee for AMS IAMP with $O(N^2\varepsilon^{-3}\log^2(e/\varepsilon))$ work but a sufficient dimension exponential in inverse accuracy. By returning a fixed configuration below its dimension threshold, GEG-IAMP also provides an asymptotic fully polynomial randomized approximation scheme (AFPRAS), with an additive error independent of dimension.

Closest papers

Nearest neighbours by meaning across the whole index.

A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP

cs.DS ·2026-09-28 ·Zhao Song
theory similarity 0.62
Abstract

Karlin, Klein, and Oveis Gharan introduced a randomized better-than-$3/2$ approximation algorithm for metric TSP [KKO21] and subsequently established the corresponding improvement in the integrality gap of the subtour-elimination LP [KKO22], with an explicit constant $\varepsilon>1.00000\cdot10^{-36}$. Gurvits, Klein, and Leake subsequently improved the certified saving to $2.18000\cdot10^{-34}$ [GKL24]. In this paper, we obtain a randomized polynomial-time $(3/2-\varepsilon)$-approximation for every fixed $0<\varepsilon<\varepsilon_\star$, where $\varepsilon_\star>2.78621\cdot10^{-18}$, and consequently the subtour-elimination LP has integrality gap at most $3/2-\varepsilon_\star$. The classical worst-case integrality-gap lower bound is $4/3$ [Wil90].

0.39

Sampling from the Sherrington-Kirkpatrick Model up to Criticality

cs.DS math.PRcond-mat.dis-nnmath-ph ·2026-10-13 ·Hang Du, Brice Huang, Sidhanth Mohanty, Amit Rajaraman
theory similarity 0.60
Abstract · 56 pages

We prove that the simulated annealing algorithm efficiently samples from the Sherrington-Kirkpatrick model at inverse temperature $β< 1$ to an arbitrary inverse polynomial accuracy in total variation.

0.37

Zero Knowledge for Free up to Linear Query Bounds: Quasilinear-Size Constant-Query Zero-Knowledge PCPs

cs.CC ·2026-10-21 ·Inhyuk Park, Chenglin Fan
theory similarity 0.59
Abstract · The abstract is shortened due to the length limit of arXiv

We show that for all polynomials $T$ and $b$, every relation in NTIME($T$) has a binary PCP with $O(1)$ non-adaptive queries, perfect completeness, soundness error 1/2 and length $(T+b)\cdot(\log(T+b))^{O(1)}$, which is perfect zero knowledge against every adaptive, possibly malicious verifier making at most $b$ queries. This improves the length $\tilde O(T+b^2)$ of Zeilberger, O'Connor, Gur and Spooner (2026), who observed that Dinur's gap amplification preserves zero knowledge. The simulator runs in expected polynomial time (or in strict polynomial time, with a failure symbol or with negligible statistical error). For $b\le T$ the length is $T\cdot\mathrm{polylog}\,T$, the form of the shortest known constant-query PCPs without zero knowledge. Unless NP $\subseteq$ BPP, the dependence on $b$ is optimal up to the polylogarithmic factor for polynomial-time simulators: zero knowledge is free up to linear query bounds. Zero-knowledge interactive oracle proofs achieved length $\tilde O(T+b)$ in 2016-17; we obtain it for PCPs. Gur, O'Connor and Spooner (STOC 2025) asked whether NP has such PCPs of quasilinear length (their Open Problem 1). This paper answers it for every polynomial query bound, with the simulators above in place of a strict polynomial-time perfect simulator. The proofs were developed with extensive AI assistance and have been checked by the authors. We mask the Reed-Solomon proof of proximity of Ben-Sasson and Sudan at every node of its recursion. By a locator lemma, at every node, whatever $k$ of its proof symbols reveal about its input is determined by $O(k)$ input values. We prove it with the coprime-order argument of Bafna and Vyas (2026); our treatment of domain points is new. Dinur's gap amplification gives constant query complexity. The query count and the polylogarithmic exponent are absolute but very large.

0.10

Color Coding for the Sherrington-Kirkpatrick Model

cs.DS math-ph ·2026-10-07 ·Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra
similarity 0.59
Abstract · 33 pages

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.

0.54

Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials

cs.DS math.STmath.PR ·2026-09-07 ·Zhangsong Li
theory similarity 0.59
Abstract · 29 pages, 2 figures; extended the results and added a detailed description of AI usage

We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is \[ \boldsymbol{Y}=\frac{1}{\sqrt{n}} \boldsymbolθ \boldsymbolθ^{\top}+\boldsymbol{W}, \] where the coordinates of $\boldsymbolθ$ are independent with a common, fixed sub-Gaussian distribution $π_Θ$ satisfying $\mathbb E[Θ]\neq0$, and $\boldsymbol{W}$ is symmetric with independent standard Gaussian upper-triangular entries. For every such prior, we give an explicit finite-dimensional bound implying that every sequence of polynomial estimators of degree $D(n)=o(n^{1/60})$ has normalized mean-square error with limit inferior at least $\mathbb E[Θ^2]-q_{\mathsf{amp}}$, the limiting error of Bayes approximate message passing (AMP). This extends the constant-degree equivalence of Montanari and Wein~\cite{montanari2025equivalence} to growing degree under the same prior assumptions. Combined with their polynomial approximation of fixed-iteration AMP, the bound identifies the exact limiting low-degree MMSE whenever $D(n)\to\infty$ within this range. It thereby answers the growing-degree AMP-equivalence question discussed in~\cite{wein2025computational, maleki2026high} for nonzero-mean sub-Gaussian priors in the stated degree range. We also obtain a moment-dependent finite-dimensional lower bound for any nonzero-mean prior with all moments finite. The proof bounds low-degree MMSE using \emph{conditional} joint cumulants and a refined application of Jensen's inequality. The conditional cumulants are defined using an auxiliary Gaussian channel $\boldsymbol{R}$ calibrated to the AMP fixed point. This retains signal dependence that is lost in unconditional cumulant bounds and produces the cancellations needed for quantitative control as the degree grows.

0.19

Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model

cs.DS math.PR ·2026-10-07 ·Zhe Hou, Jingcheng Liu, Yixiao Yu
similarity 0.59
Abstract

We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ<1$ and every fixed $M,D>0$, we give a polynomial-time simulated annealing algorithm whose output distribution is within $n^{-M}$ total-variation distance of the Gibbs distribution, with probability at least $1-n^{-D}$ over the interaction matrix. The algorithm starts from uniform product spins and uses Glauber dynamics along an increasing inverse-temperature schedule. The same approach also yields partition-function estimates with relative error $n^{-M}$. The key ingredient is a quantitative weak Poincaré inequality. Building on the stochastic-localization approach to weak Poincaré inequalities [Davies, Lee, Sandhu, and Shi, arXiv:2607.08160, 2026], we use Gaussian isoperimetry to directly compare exact stochastic localization paths. Our comparison tolerates failures of local Lipschitz continuity of the posterior mean by controlling their accumulated cost. The local Lipschitzness comes from approximating the posterior means by stationary points of the Thouless-Anderson-Palmer (TAP) free energy in locally strongly convex regions located by approximate message passing, a paradigm introduced by algorithmic stochastic localization [El Alaoui, Montanari, and Sellke, 2025; Celentano, 2024]. The approximation errors are roughly characterized by the validity of the TAP gradient equations, but in a different coordinate. To show that the errors rarely accumulate too much, we need a strong concentration control. A direct argument would require solving a variant of an open problem by Talagrand [2010, Research Problem 1.7.9]. We bypass this open problem with an intermediate conditioning step and transfer the control back by establishing the stability of the TAP gradient under deletion of coordinates.

0.39

A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization

cs.DS cs.DM ·2026-11-18 ·Mikhail Cherniavskii, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev, Fedor Ozhegov +1 more
similarity 0.58
Abstract

We study unweighted nonpreemptive throughput maximization on an arbitrary number of identical machines: each job has a processing time and a release--deadline window, and the goal is to schedule as many jobs as possible. For every fixed $\varepsilon>0$, we give a randomized $(12/11+\varepsilon)$-approximation. This improves the recent $(4/3+\varepsilon)$-approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the $(17/13+\varepsilon)$-approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time $n^{O_\varepsilon(1)}\operatorname{poly}(N)$, where $N$ is the input length.

0.28

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

cs.LG stat.MLmath.OCmath.ST ·2026-10-31 ·Denis Belomestny, Alexey Naumov, Sergey Samsonov
theory similarity 0.57
Abstract

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $γ\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-γ}+n^{γ-1}$ in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of $γ$. The nonlinear bias contributes $n^{1/2-γ}$ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order $n^{-(1-γ)/2}$ for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error $\varepsilon$ on this example takes order $\varepsilon^{-4}$ iterations for the best choice $γ=3/4$. Achieving both Gaussian approximation and relative mean variance-estimation errors at most $\varepsilon$ uniformly over the model class requires at least order $\varepsilon^{-6}$ iterations for every fixed $γ$.

0.28