PaperlayerView exact revision on arXiv

Source-linked AI summary

Color Coding for the Sherrington-Kirkpatrick Model

Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra

arXiv:2610.10443v1cs.DSmath-phmath.MP

TL;DR

Efficiently approximating typical-instance partition functions is a central computational question for mixed p-spin models. This paper uses color coding on a truncated high-temperature graph expansion, with a polynomial-time evaluation and an arbitrarily small expected squared truncation error.

  • Problem

    The paper asks whether a typical mixed p-spin instance’s partition function can be approximated efficiently to prescribed accuracy.

    Source: §1 · p. 3

  • Method

    It applies color coding to a truncated high-temperature expansion, retaining even graphs with few edges and branching vertices.

    Source: §2 · p. 7

  • Results

    For every fixed D>0, suitable cutoffs make the expected squared truncation error at most n^-D, and the retained sum is computable in polynomial time when K=O(log n).

    Source: §2 · pp. 7–8

  • Takeaways & Limitations

    The graph expansion’s leading cycle contribution can be refined with sparse graphs containing a small number of branching vertices to reach prescribed accuracy.

    Source: §2 · p. 7

    The multiplicative guarantee relies on zero-freeness in the origin-centered disk of radius β*, an event whose failure probability is bounded by ζ_n.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses efficient approximation of mixed p-spin partition functions and gives a deterministic polynomial-time algorithm throughout the second-moment regime. For the SK model, this covers the entire high-temperature phase; the algorithm applies color coding to a high-temperature graph expansion, combined with zero-freeness to obtain multiplicative guarantees.

1 Introduction

  • The motivating computational question is whether a typical instance’s partition function can be approximated efficiently to prescribed accuracy.The paper also asks which inverse temperatures permit efficient approximation.Source: §1 · p. 3

1.1 Our Results

  • The deterministic algorithm approximates mixed p-spin partition functions throughout the second-moment regime, using at most (n/(εδ))^C operations for |β|≤β*.Its guarantee holds with high probability over the disorder.Source: §1.1 · p. 4
  • For the SK model, β2nd=1, so the result gives polynomial-time counting throughout the high-temperature phase.Source: §1.1 · p. 4
  • Bencs, Huang, Lee, Liu, and Regts gave a deterministic quasipolynomial-time algorithm in the same regime; this work reduces the running time to polynomial.Their zero-freeness result is combined with Barvinok interpolation to convert Taylor approximations into multiplicative approximations.Source: §1.1 · p. 4
  • Color coding is applied to the Aizenman–Lebowitz–Ruelle high-temperature expansion, retaining sparse even graphs with few edges and branching vertices for efficient evaluation.For mixed p-spin models, the method additionally controls nonpair interactions before reducing the remaining computation to paths and cycles.Source: §1.1 · p. 5

2 Technical overview

The technical overview turns the normalized partition function into a weighted sum over even graphs, then approximates that sum by retaining a controlled family of sparse graphs. Color coding, derandomization, and dynamic programming make the estimate deterministic and polynomial-time computable.

2 Technical overview

  • The high-temperature expansion expresses the normalized partition function as an explicit prefactor times a sum over even subgraphs.The normalization factor is explicit and computable, so an estimate of the normalized function transfers with the same multiplicative error.Source: §2 · p. 6
  • The truncation retains even graphs with at most K edges and fewer than b branching vertices, refining the approximation by unions of disjoint cycles.Branching vertices have degree at least four.Source: §2 · p. 7
  • For every fixed D>0, the expected squared truncation error can be made at most n^-D by suitable cutoffs.The overview uses K=O_D(log n) edges and b=O_D(1) branching vertices.Source: §2 · p. 7
  • Color coding estimates the retained graph sum without enumerating its quasipolynomially many terms, and conditional expectations replace random colorings with deterministic ones.The coloring estimator averages over T independent balanced colorings, with polynomial T sufficient when K=O(log n).Source: §2 · pp. 7–8
  • For each coloring, grouping graphs by their branching vertices reduces evaluation to weighted path and cycle sums via dynamic programming, yielding polynomial time when K=O(log n).Source: §2 · p. 8
  • The paper extends the proof to mixed p-spin models through a corresponding expansion, truncation bound, color-coding estimator, and dynamic programming implementation.Source: §2 · p. 8

3 Proof of the main theorem

For the SK model, the proof combines graph-polynomial estimates to obtain the main approximation guarantee. It turns coefficient control into multiplicative partition-function estimation using a uniform lower bound on the normalized partition function.

3 Proof of the main theorem

  • For log n ≤ L ≤ κn, Theorems 4.1 and 5.1 combine by a triangle inequality to produce an estimate computable in polynomial time in n, ε^-1, and δ^-1.Source: §3 · p. 10
  • The proof converts coefficient error into uniform additive error, then uses a lower bound on the normalized partition function to obtain multiplicative accuracy.Source: §3 · pp. 9–10

3.2 Lower bound for the normalized partition function

  • A uniform lower bound on |Yg| over |z| ≤ β* follows by combining zero-freeness with a high-probability upper bound on a larger disk and Harnack’s inequality.Source: §3.2 · pp. 12, 14
  • The zero-free result of Bencs et al. transfers to the normalized function Yg because the normalization multipliers never vanish.Source: §3.2 · p. 12

4 Truncation bounds

This section approximates the graph expansion by truncating it and bounds the resulting squared error in a weighted coefficient norm. The retained even graphs have bounded edge counts and few branching vertices.

4 Truncation bounds

  • The truncation retains even graphs with at most K edges and fewer than b branching vertices, where branching vertices have degree at least 4.Source: §4 · p. 14
  • For n ≥ 2 and log n ≤ L ≤ κn, the edge cutoff K can be chosen as O(L), with constants depending only on λ.Source: §4 · p. 14
  • The discarded-term error is bounded by treating its two contributions separately in the weighted coefficient norm.Source: §4 · pp. 14–16

5 Deterministic estimator via color coding

The section builds a deterministic estimator for a truncated graph expansion by applying color coding, then derandomizing and evaluating the resulting sums efficiently. Its runtime is polynomial in the stated logarithmic-cutoff regime.

5 Deterministic estimator via color coding

  • The estimator is computable in poly(n)e^O(L) operations and is polynomial-time when K = O(log n) and b log(en/b) = O(log n).The section’s proposition supplies the estimator and its runtime; the dynamic program evaluates each coloring without enumerating all terms.Source: §5 · p. 16
  • Color coding weights each colorful graph by the inverse probability that its vertex set is colorful, yielding an estimator for the truncated expansion.Balanced colorings have color classes differing in size by at most one.Source: §5 · p. 16

5.2 Deterministic selection of colorings

  • The method of conditional expectations replaces random colorings with deterministic ones while preserving the estimator’s error bound.The proof maintains conditional overlap bounds as vertices are assigned colors.Source: §5 · p. 17, §5.2 · pp. 18–19

5.1 The reduction

  • The reduction combines deterministically constructed balanced colorings with exact evaluation of their associated polynomials to obtain the required error bound.The construction and evaluation cost is bounded by poly(n)e^O(L).Source: §5.1 · pp. 17–18

5.3 Dynamic programming for a fixed coloring

  • For a fixed coloring, dynamic programming groups colorful graphs by branching vertices and recorded data, then combines weighted paths, cycles, and direct edges.The number of retained data combinations is at most e^O(K), giving poly(n)e^O(K) arithmetic operations for the fixed-coloring evaluation.Source: §5.3 · pp. 20–22

A.1 The ALR expansion

This section develops the mixed-model high-temperature expansion by grouping repeated-index interactions into spin monomials. Its partition-function polynomial is expressed through even interaction sets with Gaussian-weighted coefficients.

A.1 The ALR expansion

  • Grouping Hamiltonian terms that yield the same spin monomial accounts for repeated indices in the mixed p-spin model.The expansion follows Aizenman, Lebowitz, and Ruelle.Source: §A.1 · p. 22
  • The couplings associated with nonempty interaction sets of positive variance are independent centered Gaussians.The couplings are independent because their defining sums use disjoint Gaussian entries.Source: §A.1 · p. 22
  • For each interaction set A, the expansion uses t_A(β) = tanh(βJ_A) and sums products t_F over even sets F.A set F is even when every vertex has even degree.Source: §A.1 · pp. 22–23
  • Distinct interaction sets are orthogonal under the Gaussian disorder, yielding the weighted coefficient-norm identity for real |β| ≤ β*.The argument uses an odd function of an independent centered Gaussian from the symmetric difference of the sets.Source: §A.1 · p. 23

A.2 Truncation bounds

The truncation analysis controls the weighted coefficient error after restricting the expansion to a retained family of even interaction sets. It gives cutoff choices over a specified range of accuracy parameters.

A.2 Truncation bounds

  • The retained family consists of even interaction sets with at most K edges and with both s(F) and r(F) below b.The construction tracks the number of interactions that are not pairs.Source: §A.2 · p. 23
  • For log n ≤ L ≤ κn, the truncation lemma provides cutoffs including K = O(L), with constants depending on the fixed mixture and λ.The lemma states that the resulting error terms can each be made at most e^-L/3 by choosing its constants sufficiently large.Source: §A.2 · pp. 24, 26
  • When K ≤ κ0n and κ0 is decreased until CK/n ≤ 1/4, a geometric-series argument bounds the three terms by Ce−cAL, Ce−A′L/2, and Ce−A′L/4; sufficiently large A, A′ make each at most e−L/3.Source: §A.2 · p. 26

A.3 Deterministic estimator via color coding

The mixed-model extension adapts color coding and deterministic coloring selection to retained even hypergraphs with higher-order interactions. Its evaluator incorporates those interactions while reusing the path-and-cycle dynamic program for pair interactions.

A.3 Deterministic estimator via color coding

  • Non-pair interactions are confined to a small terminal set, while supported vertices outside that set have degree two and participate only in pair interactions.The evaluator augments the existing dynamic program to handle non-uniform pair interactions within the terminal set.Source: §A.3 · pp. 26–27
  • The mixed-model evaluator computes the generalized polynomial exactly in poly(n)e^O(K)n^q* arithmetic operations for arbitrary interaction inputs.Here q* is defined as (1 + p_max)b.Source: §A.3 · pp. 27–28
  • The derandomized mixed-model estimator can be constructed and evaluated in poly(n)e^O(L) operations, with its circuit independent of disorder and temperature.The cutoffs and q* bounds yield the stated running time.Source: §A.3 · pp. 26, 29
  • Combining the approximation with the truncation bound yields a single statement for every accuracy parameter L ≥ log n.The corollary states the existence of a deterministic multilinear polynomial approximation.Source: §A.3 · p. 29

A.4 Lower bound for the normalized partition function

The section extends the lower-bound argument to the general setting, using a Harnack argument to control the normalized partition function with high probability.

A.4 Lower bound for the normalized partition function

  • Lemma A.7 supplies constants c > 0, C ≥ 1, and a sequence ζn = o(1) for every 0 < α < 1/2.The constants and sequence depend only on the mixture and fixed radii.Source: §A.4 · p. 30
  • With probability at least 1 − α, sup|z|≤R0 |YG(z)| is bounded by √(CU/α).Here CU ≥ 1 is fixed, and the bound is obtained using Markov’s inequality.Source: §A.4 · p. 30
  • The proof adapts Theorem 3.5’s Harnack argument with R0 replacing R1, yielding c = bη∗/(R0 − β∗).The cited passage states the resulting constant C = Cc.Source: §A.4 · p. 30

A.5 Proof of the main theorem

The proof applies the mixed-model approximation results to a polynomial estimator, then uses the established bounds to obtain the main theorem with polynomial construction and evaluation cost.

A.5 Proof of the main theorem

  • Lemma A.8’s bounds are applied to every deterministic multilinear polynomial and then to every deterministic multilinear approximation bP.The proof derives the bounds using the calculation from Theorem 3.3 and applies (15) to LG(bP − P).Source: §A.5 · p. 31
  • The proof takes bPL from Theorem A.6, sets bYG := LG bPL, and applies Theorems A.7 and A.8 with Markov’s inequality.The supplied passage introduces the resulting conclusion but does not include its statement.Source: §A.5 · p. 31
  • The estimator has the same relative error as bYG, and its construction and evaluation take (n/(εδ))^O(1) operations.The stated cost is poly(n)e^O(L) + O(npmax), with L chosen as Θ(log(n/(εδ))).Source: §A.5 · p. 31
Loading 2610.10443v1…