Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

CLuP practically achieves $\sim 1.77$ positive and $\sim 0.33$ negative Hopfield model ground state free energy

T0 review · 3 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that the CLuP±Hop algorithm computes near-ground-state free energies of random positive and negative Hopfield models, reaching about 1.77 and 0.33 for n in the low thousands, against thermodynamic limits of roughly…

desk verdict A genuine algorithmic extension to Hopfield models, but the numbers it advertises are compared only against the author's own unproven fl RDT framework; worth refereeing with demands for independent verification. read the letter →

arxiv 2507.22396 v1 pith:FM36FEYF submitted 2025-07-30 cond-mat.dis-nn cs.ITmath.ITmath.OCstat.ML

Mihailo Stojnic This is my paper
classification cond-mat.dis-nncs.ITmath.ITmath.OCstat.ML MSC 82B4482D30 PACS 75.10.Nr
keywords HopfieldmodelsgroundstatefreeenergyCLuPalgorithmfullyliftedrandomdualitytheorySherrington–Kirkpatrickmodelsemidefinitequadraticprogrammingbinaryoptimizationoverlapdistributions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies the ground-state free energy of random positive and negative Hopfield models, which are equivalent to maximizing $x^T A x$ over binary vectors $x \in \{\pm 1/\sqrt{n}\}^n$ with $A = G^T G$ (positive) or $A = -G^T G$ (negative) for a standard-normal random matrix $G$. It introduces the Controlled Loosening-up algorithms CLuP+Hop and CLuP−Hop, which run gradient descent on a log-barrier objective while steadily increasing a loosening parameter $t_{0x}$, and reports that for $n$ as small as a few thousand they reach ground-state free energies of approximately $1.77$ and $0.33$. These values closely approach the thermodynamic limits $\approx 1.7784$ and $\approx 0.3281$ computed by fully lifted random duality theory at the sixth lifting level, and the simulations track the theory's predicted dynamics already at the third level. If the claim stands, computing near-ground-state energies of Hopfield models is typically easy even though the same quadratic-programming problem is worst-case hard, and the sixth-level analysis exposes a structural contrast: near-optimal configurations of the positive model are typically close to one another, while those of the negative model are typically nearly orthogonal.

What carries the argument

The load-bearing object is the CLuP±Hop objective, a log-barrier function $\bar f^{\pm}_{b,x}(x;\bar t_{0x}) = -\bar t_{0x}\|x\|^2 - \log(-(x^T M^{\pm} x - \kappa)) - \frac{1}{n}\sum_i \log(1-nx_i^2)$ with $M^{+} = 4I - \frac{1}{n}G^TG$ and $M^{-} = \frac{1}{n}G^TG$, whose gradient steps keep iterates inside the cube $\{\pm 1/\sqrt{n}\}^n$ while the growing $\bar t_{0x}$ gradually loosens the auxiliary term so the procedure sharpens toward the ground state. The analytical engine is fully lifted random duality theory: Theorem 1 (imported from [78]) converts the bilinearly indexed random maximization into a deterministic lifted random dual $\bar{\psi}_{rd}$, and Theorem 2 identifies the ground-state value $\xi(r_x,\bar r_x)=f_{\rm chop}(\infty)$ with the negative of that dual, evaluated at the stationary point of $p,q,c,\gamma,\nu,\gamma_{sq}$ for lifting level $r$. The lifting level controls accuracy: level 3 already reproduces the algorithm's whole trajectory, and level 6 yields the limiting free energies and the overlap cumulative distribution functions.

What would settle it

Run an independent, certified exhaustive search at $n=200$ (or branch-and-bound at $n=400$) on the same random $G$ used in the paper, and check whether the true +Hop maximum (resp. −Hop minimum) matches CLuP±Hop's output within the paper's reported finite-$n$ gap; a systematic shortfall would falsify the near-optimality claim.

Watch

Extended reading notes

Core claim

The central claim is that the CLuP±Hop update $$$x^{{(t+1)}}$ \gets \operatorname{gradbar}\big(\bar $f^{{\pm}}$_{b,x}(x; \bar t_{0x}^{(t)}); $x^{{(t)}}$, \bar t_{0x}^{(t)}\big), \qquad \bar t_{0x}^{(t+1)} \gets $c^{{(t)}}$ \bar t_{0x}^{(t)},$$ with $c^{(t)}=1.1$, finds near-ground-state configurations of both Hopfield models: plain gradient descent on the barrier objective $\bar f^{+}_{b,x} = -\bar t_{0x}\|x\|^2 - \log(-(x^T(4I - \frac{1}{n}G^T G)x - \kappa)) - \frac{1}{n}\sum_i \log(1 - n x_i^2)$ (and the analogous $0I$ form for −Hop) reaches $\hat\xi \approx 1.7704$–$1.7735$ for +Hop and $\approx 0.3355$–$0.3330$ for −Hop at $n = 2000$–$8000$. The paper derives these dynamics from fully lifted random duality theory: Theorem 2 expresses the ground-state value $\xi(r_x,\bar r_x) = f_{\rm chop}(\infty)$ as the negative of a lifted random dual whose stationary conditions are solved at lifting levels $r=2,\dots,6$, giving thermodynamic limits $f^{+,6}_{sq}(\infty)\approx 1.77842$ and $f^{-,6}_{sq}(\infty)\approx -0.32807$ (the −Hop value reported as a positive minimum). It then reads the overlap structure off the same sixth-level solution: the Gibbs-measure overlap distributions show +Hop near-optimal configurations typically close to each other and −Hop configurations typically almost orthogonal, with the Sherrington–Kirkpatrick overlap behavior resembling +Hop rather than −Hop.

Load-bearing premise

The claimed agreement stands on an imported theorem that characterizes the thermodynamic limits; the theorem's proof is not given here but deferred to earlier work, so if that theorem or its numerical solution is inaccurate, the algorithm is being compared with a self-generated target.

Editorial extensions

If this is right

  • For $n=2000$–$8000$, restart-free CLuP±Hop reaches $\hat\xi \approx 1.7704$–$1.7735$ (+Hop) and $\approx 0.3355$–$0.3330$ (−Hop), approaching the thermodynamic limits $\approx 1.7784$ and $\approx 0.3281$ closely enough to call the near-ground-state problem typically easy.
  • The approximation factor for random ±Hop instances can be pushed toward 1, so the worst-case NP-hardness of indefinite quadratic programming does not manifest on typical instances.
  • Restarting and retuning the factor $c^{(t)}$ (e.g., $c^{(t)} = \mathrm{Unif}[1,1.3]$) further cuts finite-$n$ error, improving −Hop at $n=500$ from $0.3430$ to $0.3358$, so plain descent is not the ceiling.
  • The sixth-level overlap distributions say that +Hop near-optimal configurations are typically close to each other and −Hop configurations are typically almost orthogonal; the Sherrington–Kirkpatrick model's overlap distribution resembles +Hop.
  • The same lifting progression gives $f^{(7)}_{csk}(\infty) \approx 0.76319$ for the SK model at the seventh level, supporting the existing predictions $\approx 0.76321 \pm 0.00003$ and $\approx 0.76317$ for its true ground-state free energy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the thermodynamic targets come from the paper's own fully lifted random duality theory, the numerical agreement is currently a self-consistency check; an independent derivation or proof of Theorem 1's limits would turn the close agreement into a genuine validation.
  • The +Hop/−Hop overlap dichotomy suggests a practical rule of thumb the paper does not systematically test: for −Hop, many well-separated restarts matter more than careful local refinement, while for +Hop a single good run suffices.
  • The observed no-local-optima landscape suggests CLuP-style annealing may transfer to other bilinearly indexed random-process models; testing it on $p$-spin or planted analogues at matched $n$ would reveal whether the favorable landscape is a generic feature.
  • The finite-$n$ gaps ($1.7784 - \hat\xi_+$, $0.3281 - \hat\xi_-$) appear to shrink steadily with $n$; fitting their decay rate would let practitioners predict the dimension needed for any target accuracy, an extrapolation the paper leaves implicit.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies the problem of approximating ground-state free energies of positive and negative Hopfield models, i.e., maximizing x^T G^T G x or -x^T G^T G x over binary {±1/√n}^n vectors with Gaussian G. It introduces a CLuP±Hop gradient-descent algorithm, reports finite-n simulations (n up to 8000) reaching ξ≈1.77 for +Hop and ≈0.33 (magnitude) for -Hop, and compares these with thermodynamic-limit values ≈1.7784 and ≈0.3281 computed from the author's fully lifted random duality theory (fl RDT) at the sixth lifting level. The paper also studies overlap distributions, reports a qualitative difference between +Hop and -Hop near-optimal configurations, and concludes that these problems are 'typically easy.'

Significance. If the imported fl RDT characterization is correct and the simulations are reproducible, the paper gives a concrete algorithmic heuristic that appears to find near-ground-state configurations of random Hopfield models at moderate n, and the overlap cdfs in Figures 8-10 are testable predictions. The strengths are the breadth of the empirical study—finite-size convergence, concentration histograms, landscape evaluation, and comparison with SK—and the explicit falsifiable numbers in Tables 3-5. However, the main theoretical benchmark is not established in this paper: the strong-duality theorem is imported from the author's own preprints, and the reported agreement is between the algorithm and a self-generated prediction. The significance is therefore conditional on independent verification of the theory column.

major comments (3)
  1. [§3, Theorem 1 (Eq. 33)] The proof of Theorem 1 is one sentence: 'Follows immediately from [74, 78] after trivial cosmetic changes in the definition of set X.' The set X(rx,r̄x) in Eq. (14) is nonconvex and carries the entropy constraint (1/n)Σ log(1 - n x_i^2) = r̄x; no verification is given that the strong sfl RDT duality (33) holds for this domain, nor that the stationary point of system (46) selected by the numerics is the correct global extremum. Because Eq. (41) identifies f_chop(∞) with -ψ_rd and Table 1's theory column is computed from this identification, the agreement reported in Table 1 is currently an agreement between the algorithm and a self-generated prediction. This is load-bearing for the central claim that CLuP±Hop practically achieves the ground state free energies. I would need either a proof/check of the theorem's hypotheses for X(rx,r̄x) (with a precise reference to the result in [74,78] being invoked), or an independent benchmark—e.g., exact brute-force values for small n, rigorous bounds, or results from another group—against which both the algorithm and the 6-spl numbers are tested.
  2. [§3.2.1 and Tables 3–4] The 6-spl numbers 1.77842 and 0.32807 are quoted to five significant digits, but the paper does not report the numerical procedure used to solve the stationarity system (46), any error bars, or a check that the solution is stable under changes of discretization or initialization. The finite-n gaps in Table 1 (e.g., +Hop: 1.7735 at n=8000 vs 1.7784; -Hop: 0.3330 vs 0.3281) are then impossible to interpret as purely finite-size effects, because the theory column itself has no stated precision. Providing code (or at least a detailed solver description plus a sensitivity analysis) and an independent validation of the 6-spl values would materially strengthen the paper.
  3. [§4 and abstract] The conclusion that ±Hop ground state problems are 'typically easy' is stronger than the evidence presented. The paper demonstrates empirically that a particular heuristic without restarts comes close to the claimed limits for n up to 8000, but it provides no runtime scaling analysis, no statement about typical-case polynomial time, and no overlap-gap-property style evidence; the 'no local optima' observation in Figure 7 is a numerical evaluation of the 3-spl RDT surrogate objective at selected t0x, not of the original optimization landscape. I recommend either supplying a formal typical-case statement or tempering the claim to 'empirically easy for the tested system sizes.'
minor comments (6)
  1. [§2.1] The spectral lower bound is written as '2√2/π' but then as '√(8/π)'; since 2√(2/π)=√(8/π) and 2√2/π≈0.900, one of these expressions is a typo. Please correct.
  2. [§2, Eqs. (7)-(8) vs Table 1] The negative-model free energy f^-_sq(∞) is defined as a negative quantity in Eq. (8), but Table 1 and the abstract report '0.33' and '0.3281' as positive magnitudes. Please state the sign convention explicitly so that the negative-model free energy is not presented with the wrong sign.
  3. [§2, Eq. (12)] The quantity ξhat is defined with an expectation E_G, but in the simulations it is an empirical average over algorithm outputs for fixed G; the notation should distinguish the random quantity from its expectation.
  4. [§3.2.2] The sentence 'Table 4 to +Hop model' should read 'Table 4 to -Hop model.'
  5. [Conclusion] The term '3-spf RDT' should be '3-spl RDT.'
  6. [§3, Eq. (30)] The expression 's max_{x∈Y, ∥y∥=...}' contains a typo; the maximization over Y should be over y.

Circularity Check

2 steps flagged · score 6.0 of 10

The 1.7784/0.3281 'thermodynamic limits' are imported from the author's own fl RDT chain ([74,78,80]); Table 1 validates CLuP±Hop against a self-generated benchmark.

  1. self citation load bearing [Section 3, Theorem 1 (Eqs. 27-33)]
    "The following theorem is a fundamental sfl RDT result. Theorem 1 ([78]). ... assume the complete sfl RDT frame from [74]. ... Then, lim ... (strong sfl random duality). ... Proof. Follows immediately from [74, 78] after trivial cosmetic changes in the definition of set X."

    Theorem 1 is the only bridge from the CLuP±Hop model (13)-(18) to the variational formulas (34)-(49) and therefore to every 'theory' value in Table 1 and Figures 1-6. Its proof is not given; it is a direct citation to the author's own arXiv preprints [74,78]. The paper asserts the 'complete sfl RDT frame' but never checks its hypotheses for the nonconvex, entropy-constrained set X(rx, r̄x) of Eq. (14). Consequently the thermodynamic limits ≈1.7784 and ≈0.3281 are outputs of an unverified self-citation chain, and comparing CLuP±Hop to these numbers does not constitute an independent test of whether the algorithm finds the true ground state free energies.

  2. self citation load bearing [Section 3.2.2, Tables 3-4 and Table 1]
    "Concrete numerical values for p, q, and c up to the 6th lifting level are given in Tables 3 and 4 [80] (Table 3 relates to +Hop and Table 4 to +Hop model; in addition to p, q, and c the rth level values of f+sq(∞) and f−sq(∞), f+,r sq (∞) and f−,r sq (∞), are given as well; ...)."

    The abstract says 'we obtain on the 6th level of lifting (6-spl RDT) corresponding theoretical thermodynamic limits', but the actual 6th-level numbers are reproduced from [80], another same-author preprint, as the text itself states. The '∞ (theory)' column in Table 1 is thus a self-generated benchmark: the paper's validation consists of matching new finite-n simulation outputs to the same author's earlier fl RDT computations. Without independent exact small-n results, other-group calculations, or rigorous bounds, the close agreement in Table 1 is internal consistency rather than external confirmation.

full rationale

The finite-n CLuP±Hop results in Table 1 (e.g., 1.7704, 1.7721, 1.7735 for +Hop and 0.3355, 0.3340, 0.3330 for −Hop) are genuine gradient-descent simulations with independent empirical content; they are not fitted parameters disguised as predictions, so the paper is not fully circular. The circularity lies in the benchmark against which these simulations are validated. The '∞ (theory)' column (1.7784, 0.3281) is not an independent ground truth: it is obtained from Theorem 1, whose proof is a one-line citation to the author's own unverified arXiv preprints [74,78], and whose 6-spl numerical values are reproduced from the same author's [80] (Section 3.2.2, Tables 3-4). No independent exact small-n checks, other-group computations, or rigorous bounds are supplied to confirm that the stationarity system (46) selects the correct root and that the 'complete sfl RDT frame' hypotheses hold for the entropy-constrained nonconvex set X(rx, r̄x) of Eq. (14). The agreement in Table 1 and Figures 1-6 is therefore an internal consistency check between a new algorithm and a self-generated prediction, not an external validation. I assign a score of 6 rather than higher because the central theoretical limits reduce to a self-citation chain, but the algorithmic finite-n performance claims themselves contain independent numerical content that is not manufactured by the theory.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The central claim relies on the author's fl RDT framework, which is imported from self-cited preprints and not independently established. The algorithm's hyperparameters are free but appear to have minor influence. No new physical entities are introduced.

free parameters (3)
  • kappa = 0.855 (+Hop), 0.115 (-Hop)
    Hand-tuned barrier parameter in the log objective functions (10) and (11). The paper states the procedure is not overly sensitive to it.
  • t0x(0) = 0.1 (+Hop), 0.001 (-Hop)
    Initial value of the loosening parameter in the CLuP update rule (9).
  • c(t) = 1.1 (or Unif[1,1.3] in retuning)
    Multiplicative factor for updating t0x each iteration.
assumptions (3)
  • ad hoc to paper Theorem 1 (sfl random duality) gives the exact thermodynamic limit of the random primal free energy.
    The proof is deferred to the author's own prior work [74,78]; the paper provides no self-contained derivation.
  • ad hoc to paper The complete sfl RDT frame from [74] applies to the CLuP±Hop model with the set X as defined in (14).
    Imported without proof; the paper notes only 'trivial cosmetic changes' in the definition of set X.
  • standard math The beta-to-infinity and n-to-infinity limits commute in (5)-(6), so the ground state free energy equals the zero-temperature limit of the free energy.
    Assumed implicitly in equations (5)-(8); this interchange is standard in statistical mechanics though not rigorously proven for all models.

how reviews work

0 comments
Cite this review

Pith. "Pith review of CLuP practically achieves $\sim 1.77$ positive and $\sim 0.33$ negative Hopfield model ground state free energy." pith.science (2026). https://pith.science/paper/FM36FEYF

@misc{pith2026250722396,
  author       = {Pith},
  title        = {Pith review of: CLuP practically achieves $\sim 1.77$ positive and $\sim 0.33$ negative Hopfield model ground state free energy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FM36FEYF}},
  note         = {Machine review of arXiv:2507.22396}
}
abstract

We study algorithmic aspects of finding $n$-dimensional \emph{positive} and \emph{negative} Hopfield ($\pm$Hop) model ground state free energies. This corresponds to classical maximization of random positive/negative semi-definite quadratic forms over binary $\left \{\pm \frac{1}{\sqrt{n}} \right \}^n$ vectors. The key algorithmic question is whether these problems can be computationally efficiently approximated within a factor $\approx 1$. Following the introduction and success of \emph{Controlled Loosening-up} (CLuP-SK) algorithms in finding near ground state energies of closely related Sherrington-Kirkpatrick (SK) models [82], we here propose a CLuP$\pm$Hop counterparts for $\pm$Hop models. Fully lifted random duality theory (fl RDT) [78] is utilized to characterize CLuP$\pm$Hop \emph{typical} dynamics. An excellent agreement between practical performance and theoretical predictions is observed. In particular, for $n$ as small as few thousands CLuP$\pm$Hop achieve $\sim 1.77$ and $\sim 0.33$ as the ground state free energies of the positive and negative Hopfield models. At the same time we obtain on the 6th level of lifting (6-spl RDT) corresponding theoretical thermodynamic ($n\rightarrow\infty$) limits $\approx 1.7784$ and $\approx 0.3281$. This positions determining Hopfield models near ground state energies as \emph{typically} easy problems. Moreover, the very same 6th lifting level evaluations allow to uncover a fundamental intrinsic difference between two models: $+$Hop's near optimal configurations are \emph{typically close} to each other whereas the $-$Hop's are \emph{typically far away}.

Figures

Figures reproduced from arXiv: 2507.22396 by the authors.

Figure 1
Figure 1. f¯b(ˆrx) t0x as a function of t0x; +Hop (left) and −Hop (right) 3.2.2 Properties The conducted experiments allowed also to look at several interesting properties in more detail. Convergence with respect to n The theoretical results are obtained in the thermodynamic limit with n → ∞. Since only finite n’s can be simulated, it is interesting to see how quickly simulated results converge as n increases. We focus on key… view at source ↗
Figure 2
Figure 2. ¯ξ(ˆrx) as a function of t0x; +Hop (left) and −Hop (right) t0x and observed the same trend. Such an absence of objective’s local optima is a necessary condition for successful generic running of descending algorithms. To what degree (if any) intrinsic features other than objective landscape impact performance of descending algorithms remains to be seen. Studying potential presence/absence of “near optimal” solutions… view at source ↗
Figure 3
Figure 3. rˆx as a function of t0x; +Hop (left) and −Hop (right) Gibbs measures concentrate on p2, p3, . . . , pr and q2, q3, . . . , qr. In [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Convergence of ¯ξ(ˆrx) as n grows; +Hop (left) and −Hop (right) 10 as well as f (r) csk (the rth level SK ground state free energy) are not expected to significantly change). It is interesting to note that SK overlaps cdf is much more similar to +Hop than to −Hop. Furt…
Figure 5
Figure 5. Figure 5: Convergence of limt0x→∞ ξ(ˆrx) and limt0x→∞ ˆξ(ˆrx) as n grows; +Hop (left) and −Hop (right) associated performance measure. One notable exception is the characterization of the configurational overlaps and their GIbbs measures. To handle these much higher levels of li…
Figure 6
Figure 6. Figure 6: Concentration effect; +Hop (top) and −Hop (bottom) [8] A. Auffinger and W.-K. Chen. The Parisi formula has a unique minimizer. Communications in Mathe￾matical Physics, 335(3), 2015. [9] A. Auffinger, W.-K. Chen, and Q. Zheng. The SK model is infinite step replica symme…
Figure 7
Figure 7. Figure 7: Landscape as a function of rx; +Hop (left) and −Hop (right) [14] A. Barra, G. Genovese, and F. Guerra. Equlibrium statistical mechanics of bipartite spin systems. Journal of Physics A: Mathematical and Theoeretical, 44(245002), 2011. [15] A. Barra, G. Genovese, F. Guer…
Figure 8
Figure 8. Figure 8: p overlaps; +Hop (left) and −Hop (right) [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. Figure 9: q overlaps; +Hop (left) and −Hop (right) [53] D. Panchenko. The Ghirlanda-Guerra identities for mixed p-spin model. Comptes Rendus Mathematique, 348(3-4):189–192, 2010. [54] D. Panchenko. The Parisi ultrametricity conjecture. Ann. Math., 77(1):383–393, 2013. [55] D. Pa…
Figure 10
Figure 10. Figure 10: q overlap; SK model [67] M. Stojnic. A framework for perfromance characterization of LASSO algortihms. available online at http://arxiv.org/abs/1303.7291. [68] M. Stojnic. Various thresholds for ℓ1-optimization in compressed sensing. available online at http:// arxiv.…

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection

    cs.LG 2026-04 unverdicted novelty 7.0 of 10

    Upper bounds on ultrametric OGPs at levels 1 and 2 for symmetric binary perceptrons are approximately 1.6578 and 1.6219, closely matching the 3rd and 4th lifting-level parametric RDT estimates, supporting conjectures ...

Reference graph

Works this paper leans on

92 extracted references · 71 canonical work pages · cited by 1 Pith paper

  1. [78]

    M. Stojnic. Fully lifted random duality theory. 2023. a vailable online at http://arxiv.org/abs/2312. 00070

    work page 2023

  2. [1]

    Achlioptas, A

    D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms , 38(3):251–268, 2011

    2011

  3. [2]

    Addario-Berry and P

    L. Addario-Berry and P. Maillard. The algorithmic hardn ess threshold for continuous random energy models. Math. Stat. Learn. , 2:77–101, 2019

    2019

  4. [3]

    A. E. Alaoui, A. Montanari, and M. Sellke. Sampling from t he Sherrington-Kirkpatrick gibbs measure via algorithmic stochastic localization. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2 022, pages 323–334. IEEE, 2022

    2022

  5. [4]

    A. E. Alaoui, A. Montanari, and M. Sellke. Shattering in p ure spherical spin glasses. Communications in Mathematical Physics , 406(111), 2025

    2025

  6. [5]

    D. Amit, H. Gutfreund, and H. Sompolinsky. Statistical m echanics of neural networks. Annals of Physics, 173:30–47, 1987

    1987

  7. [6]

    D. J. Amit, H. Gutfreund, and H. Sompolinsky. Storing infi nite number of patterns in a spin glass model of neural networks. Phys. Rev. Letters , 55:1530, 1987

    1987

  8. [7]

    Arora, E

    S. Arora, E. Berger, E. Hazan, G. Kindler, and M. Safra. On non-approximability for quadratic pro- grams. In 46th Annual IEEE Symposium on Foundations of Computer Scienc e (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings , pages 206–215. IEEE Computer Society, 2005. 17 ˆξ 1.7 1.72 1.74 1.76 1.78 1.8 1.82 pdf of ˆξ 0 50 100 150 200 250 300...

    2005

Show all 92 references
  1. [8]

    Auffinger and W.-K

    A. Auffinger and W.-K. Chen. The Parisi formula has a unique minimizer. Communications in Mathe- matical Physics, 335(3), 2015

    2015

  2. [9]

    Auffinger, W.-K

    A. Auffinger, W.-K. Chen, and Q. Zheng. The SK model is infini te step replica symmetry breaking at zero temperature. Comm. Pure Appl. Math. , 73, 2020

    2020

  3. [10]

    Baldassi, A

    C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, a nd R. Zecchina. Subdominant dense clusters allow for simple learning and high computational performance in n eural networks with discrete synapses. Physical Review letters , 115(12):128101, 2015

    2015

  4. [11]

    Baldassi, A

    C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, a nd R. Zecchina. Local entropy as a measure for sampling solutions in constraint satisfaction problems. Journal of Statistical Mechanics: Theory and Experiment, (2):021301, 2016

    2016

  5. [12]

    Baldassi, R

    C. Baldassi, R. D. Vecchia, C. Lucibello, and R. Zecchin a. Clustering of solutions in the symmetric binary perceptron. Journal of Statistical Mechanics: Theory and Experiment , (7):073303, 2020

    2020

  6. [13]

    Barra, G

    A. Barra, G. Genovese, and F. Guerra. The replica symmet ric approximation of the analogical neural network. J. Stat. Physics , July 2010. 18 rx 0.6 0.7 0.8 0.9 1 ¯fb(rx) t0x -0.75 -0.7 -0.65 -0.6 -0.55 -0.5 Optimum (3rd partial level): ˆrx = 0.9090, ¯fb(ˆrx) t0x = − 0.7477, ξ...

    2010

  7. [14]

    Barra, G

    A. Barra, G. Genovese, and F. Guerra. Equlibrium statis tical mechanics of bipartite spin systems. Journal of Physics A: Mathematical and Theoeretical , 44(245002), 2011

    2011

  8. [15]

    Barra, G

    A. Barra, G. Genovese, F. Guerra, and D. Tantari. How gla ssy are neural networks. J. Stat. Mechanics: Thery and Experiment , July 2012

    2012

  9. [16]

    Bayati and A

    M. Bayati and A. Montanari. The dynamics of message pass ing on dense graphs, with applications to compressed sensing. IEEE Trans. Inf. Theory , 57(2):764–785, 2011

    2011

  10. [17]

    Bayati and A

    M. Bayati and A. Montanari. The LASSO risk for gaussian m atrices. IEEE Trans. Inf. Theory , 58(4):1997–2017, 2012

    1997

  11. [18]

    Bovier and V

    A. Bovier and V. Gayrard. Hopfield models as generalized random mean field models. In mathematical aspects of spin glasses and neural networks, Progr. Prob. , 41:3–89, 1998

    1998

  12. [19]

    Charikar and A

    M. Charikar and A. Wirth. Maximizing quadratic program s: Extending grothendieck’s inequality. In 45th Symposium on Foundations of Computer Science (FOCS 200 4), 17-19 October 2004, Rome, Italy, Proceedings, pages 54–60. IEEE Computer Society, 2004

    2004

  13. [20]

    Crisamti, D

    A. Crisamti, D. J. Amit, and H. Gutfreund. Saturation le vel of the Hopfield model for neural network. Europhys. Lett., (2):337, 1986

    1986

  14. [21]

    Crisanti and T

    A. Crisanti and T. Rizzo. Analysis of the ∞-replica symmetry breaking solution of the Sherrington- Kirkpatrick model. Phys. Rev. E , 65(4):046137, Apr 2002

    2002

  15. [22]

    Daude, M

    H. Daude, M. Mezard, T. Mora, and R. Zecchina. Pairs of sa t-assignments in random boolean formulae. Theoretical Computer Science, 393(1):260–279, 2008

    2008

  16. [23]

    Dean and F

    D. Dean and F. Ritort. Squared interaction matrix Sherr ington-Kirkpatrick model for a spin glass. Phys. Rev. B , 65:224209, 2002

    2002

  17. [24]

    Donoho, A

    D. Donoho, A. Maleki, and A. Montanari. Message-passin g algorithms for compressed sensing. Proc. National Academy of Sciences , 106(45):18914–18919, Nov. 2009

    2009

  18. [25]

    D. L. Donoho, A. Maleki, and A. Montanari. The noise-sen sitivity phase transition in compressed sensing. IEEE Trans. Inf. Theory , 57(10):6920–6941, 2011. 19 Table 3: r-sfl RDT parameters; +Hop model; α = 1; ˆc1 → 1;n,β → ∞ r ˆγsq [ ˆpr−1 ˆpr−2 ... ˆp1 ] T [ ˆqr−1 ˆqr−2 ... ˆq...

    2011

  19. [26]

    S. F. Edwards and P. W. Anderson. J. phys. f. 5:965, 1975

    1975

  20. [27]

    J. Feng, M. Shcherbina, and B. Tirozzi. On the critical c apacity of the Hopfield model. Communications in Mathematical Physics , 2000

    2000

  21. [28]

    Gamarnik

    D. Gamarnik. The overlap gap property: A topological ba rrier to optimizing over random structures. Proceedings of the National Academy of Sciences , 118(41), 2021

    2021

  22. [29]

    Gamarnik and M

    D. Gamarnik and M. Sudan. Limits of local algorithms ove r sparse random graphs. Proceedings of the 5th conference on innovations in theoretical computer scie nce, pages 369–376, 2014

    2014

  23. [30]

    Gamarnik and M

    D. Gamarnik and M. Sudan. Limits of local algorithms ove r sparse random graphs. Ann. Probab. , 45(4):2353–2376, 2017

    2017

  24. [31]

    Gamarnik and M

    D. Gamarnik and M. Sudan. Performance of sequential loc al algorithms for the random NAE-K-SAT problem. SIAM Journal on Computing , 46(2):590–619, 2017

    2017

  25. [32]

    F. Guerra. Broken replica symmetry bounds in the mean fie ld spin glass model. Comm. Math. Physics , 233:1–12, 2003

    2003

  26. [33]

    D. O. Hebb. Organization of behavior. New York: Wiley , 1949

    1949

  27. [34]

    J. J. Hopfield. Neural networks and physical systems wit h emergent collective computational abilities. Proc. Nat. Acad. Science , 79:2554, 1982

    1982

  28. [35]

    Huang and M

    B. Huang and M. Sellke. Tight lipschitz hardness for opt imizing mean field spin glasses. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2 022, Denver, CO, USA, October 31 - November 3, 2022 , pages 312–322. IEEE, 2022. 20 Table 4: r-sfl RDT parameters; −...

    2022

  29. [36]

    Jagannath and I

    A. Jagannath and I. Tobasco. A dynamic programming appr oach to the Parisi functional. In Proceedings of the American Mathematical Society , volume 14, pages 3135–3150

  30. [37]

    Kabashima

    Y. Kabashima. A CDMA multiuser detection algorithm on t he basis of belief propagation. L. Phys. A , 36

  31. [38]

    Kirkpatrick and D

    S. Kirkpatrick and D. Sherrington. Phys. Rev. B , 17:4384, 1978

    1978

  32. [39]

    Krotov and J

    D. Krotov and J. J. Hopfield. Dense associative memory fo r pattern recognition. Advances in Neural Information Processing Systems , 1:1180–1188, 2016

    2016

  33. [40]

    Loukianova

    D. Loukianova. Capacite de memoire dans le modele de Hop field. C. R. Acad. Sci. Paris t. 318, Serie I, pages 157–160, 1994

    1994

  34. [41]

    Loukianova

    D. Loukianova. Etude rigoureuse du modele de Hopfield de memoire associative. These de doctorat de l’Universite Paris 7 , 1994

    1994

  35. [42]

    Loukianova

    D. Loukianova. Lower bounds on the restitution error in the Hopfield model. Probab. Theory Related Fields, 107:161–176, 1997

    1997

  36. [43]

    R. J. MacEliece, E. C. Posner, E. Rodemich, and S.S. Venk atesh. The capacity of the Hopfield associative memory. IEEE Trans. Inform. Theory , 33:461–482, 1987

    1987

  37. [44]

    Megretski

    A. Megretski. Relaxation of quadratic programs in oper ator theory and system analysis. In In Systems, Approximation, Singular Integral Operators, and Related Top ics (Bordeaux), pages 365–92, 2000

    2000

  38. [45]

    Mezard, T

    M. Mezard, T. Mora, and R. Zecchina. Clustering of solut ions in the random satisfiability problem. Physical Review Letters , 94:197204, 2005. 21 c c∞ 0 0.2 0.4 0.6 0.8 1 p 0 0.2 0.4 0.6 0.8 1 p as a function of c c∞ Theory (3-spl RDT) Theory (4-spl RDT) Theory (5-spl RDT) Theo...

    2005

  39. [46]

    Montanari

    A. Montanari. Optimization of the Sherrington-Kirkpa trick hamiltonian. In 60th IEEE Annual Sym- posium on Foundations of Computer Science, FOCS 2019, Balti more, Maryland, USA, November 9-12, 2019, pages 1417–1433. IEEE Computer Society, 2019

    2019

  40. [47]

    Nesterov

    Y. Nesterov. Quality of semidefinite relaxation for non convex quadratic optimization. CORE discussion paper, 9719, 1997

    1997

  41. [48]

    Ch. M. Newman. Memory capacity and neural network model s: Rigorous lower bounds. Neural Net- works, 1:223–238, 1988

    1988

  42. [49]

    Oppermann and M

    R. Oppermann and M. J. Schmidt. Universality class of re plica symmetry breaking, scaling behavior, and the low-temperature fixed-point order function of the Sh errington-Kirkpatrick model. Phys. Rev. E, 78(6):061124, Dec 2008

    2008

  43. [50]

    Oppermann, M

    R. Oppermann, M. J. Schmidt, and D. Sherrington. Double criticality of the Sherrington-Kirkpatrick model at t = 0. Phys. Rev. Lett. , 98(12):127201, Mar 2007

    2007

  44. [51]

    Oppermann and D

    R. Oppermann and D. Sherrington. Scaling and renormali zation group in replica-symmetry-breaking space: Evidence for a simple analytical solution of the Sher rington-Kirkpatrick model at zero tempera- ture. Phys. Rev. Lett. , 95(19):197203, Nov 2005

    2005

  45. [52]

    Panchenko

    D. Panchenko. A connection between the Ghirlanda-Guer ra identities and ultrametricity. The Annals of Probability, 38(1):327–347, 2010. 22 c c2 0 0.2 0.4 0.6 0.8 1 q 0 0.2 0.4 0.6 0.8 1 q as a function of c c2 Theory (3-spl RDT) Theory (4-spl RDT) Theory (5-spl RDT) Theory (6-...

    2010

  46. [53]

    Panchenko

    D. Panchenko. The Ghirlanda-Guerra identities for mix ed p-spin model. Comptes Rendus Mathematique, 348(3-4):189–192, 2010

    2010

  47. [54]

    Panchenko

    D. Panchenko. The Parisi ultrametricity conjecture. Ann. Math. , 77(1):383–393, 2013

    2013

  48. [55]

    Panchenko

    D. Panchenko. The Sherrington-Kirkpatrick model . Springer Science & Business Media, 2013

    2013

  49. [56]

    G. Parisi. Infnite number of order parameters for spin- glasses. Phys. Rev. Lett. , 43:1754–1756, 1979

    1979

  50. [57]

    G. Parisi. Breaking the symmetry in SK model. J. Physics , A13:1101, 1980

    1980

  51. [58]

    G. Parisi. A sequence of approximated solutions to the S K model for spin glasses. Journal of Physics A: Mathematical and General , 13(4):L115, 1980

    1980

  52. [59]

    G. Parisi. Order parameter for spin glasses. Phys. Rev. Lett. , 50:1946, 1983

    1946

  53. [60]

    Pastur and A

    L. Pastur and A. Figotin. Exactly soluble model of a spin -glass. Soviet J. of Low Temperature Phys. , 3(378-383), 1977

    1977

  54. [61]

    Pastur and A

    L. Pastur and A. Figotin. On the theory of disordered spi n systems. Theory Math. Phys. , 35(403-414), 1978

    1978

  55. [62]

    Pastur, M

    L. Pastur, M. Shcherbina, and B. Tirozzi. The replica-s ymmetric solution without the replica trick for the Hopfield model. Journal of Statistical Physics , 74(5/6), 1994

    1994

  56. [63]

    Ramsauer, B

    H. Ramsauer, B. Schafl, J. Lehner, P. Seidl, M. Widrich, L . Gruber, M. Holzleitner, T. Adler, D. Kreil, M. K. Kopp, G. Klambauer, J. Brandstetter, and S. Hochreiter . Hopfield networks is all you need. In International Conference on Learning Representations , 2021

    2021

  57. [64]

    Shcherbina and B

    M. Shcherbina and B. Tirozzi. The free energy of a class o f Hopfield models. Journal of Statistical Physics, 72(1/2), 1993

    1993

  58. [65]

    Sherrington and S

    D. Sherrington and S. Kirkpatrick. Solvable model of a s pin-glass. Phys. Rev. Lett. , 35:1792–1796, Dec 1975

    1975

  59. [66]

    Steffan and R

    H. Steffan and R. Kuhn. Replica symmetry breaking in attr actor neural network models. Z. Phys. B , 95:249–260, 1994. 23 c c2 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 q 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 q as a function of c c2 – lifting progress Theory (3-spl RDT) Theory (...

    1994

  60. [67]

    M. Stojnic. A framework for perfromance characterizat ion of LASSO algortihms. available online at http://arxiv.org/abs/1303.7291

    arXiv

  61. [68]

    M. Stojnic. Various thresholds for ℓ1-optimization in compressed sensing. available online at http:// arxiv.org/abs/0907.3666

    arXiv

  62. [69]

    M. Stojnic. Recovery thresholds for ℓ1 optimization in binary compressed sensing. ISIT, IEEE Inter- national Symposium on Information Theory , pages 1593 – 1597, 13-18 June 2010. Austin, TX

    2010

  63. [70]

    M. Stojnic. Bounding ground state energy of Hopfield mod els. 2013. available online at http://arxiv. org/abs/1306.3764

    2013 arXiv

  64. [71]

    M. Stojnic. Lifting/lowering Hopfield models ground st ate energies. 2013. available online at http:// arxiv.org/abs/1306.3975

    2013 arXiv

  65. [72]

    M. Stojnic. Controlled loosening-up (CLuP) – achievin g exact MIMO ML in polynomial time. 2019. available online at http://arxiv.org/abs/1909.01175

    2019 arXiv

  66. [73]

    M. Stojnic. Sparse linear regression – CLuP achieves th e ideal exact ml. 2020. available online at http://arxiv.org/abs/2011.11550

    2020 arXiv

  67. [74]

    M. Stojnic. Bilinearly indexed random processes – stationarization of fully lifted interpolation. 2023. available online at http://arxiv.org/abs/2311.18097

    2023 arXiv

  68. [75]

    M. Stojnic. Binary perceptrons capacity via fully lift ed random duality theory. 2023. available online at http://arxiv.org/abs/2312.00073

    2023 arXiv

  69. [76]

    M. Stojnic. Fl rdt based ultimate lowering of the negati ve spherical perceptron capacity. 2023. available online at http://arxiv.org/abs/2312.16531

    2023 arXiv

  70. [77]

    M. Stojnic. Fully lifted interpolating comparisons of bilinearly indexed random processes. 2023. available online at http://arxiv.org/abs/2311.18092

    2023 arXiv

  71. [79]

    M. Stojnic. Lifted rdt based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networks. 2023. available online at http://arxiv.org/abs/2312.08257. 24

    2023 arXiv

  72. [80]

    M. Stojnic. Studying Hopfield models via fully lifted ra ndom duality theory. 2023. available online at http://arxiv.org/abs/2312.00071

    2023 arXiv

  73. [81]

    M. Stojnic. Capacity of the Hebbian-Hopfield network as sociative memory. 2024. available online at http://arxiv.org/abs/2403.01907

    2024 arXiv

  74. [82]

    M. Stojnic. A CLuP algorithm to practically achieve ∼ 0.76 SK–model ground state free energy. 2025. available online at http://arxiv.org/abs/2507.09247

    2025 arXiv

  75. [83]

    M. Stojnic. Rare dense solutions clusters in asymmetri c binary perceptrons – local entropy via fully lifted RDT. 2025. available online at http://arxiv.org/abs/2506.19276

    2025 arXiv

  76. [84]

    The complexity of spherical p-spin models - A se cond moment approach

    E Subag. The complexity of spherical p-spin models - A se cond moment approach. Ann. Probab. , 45:3385 – 3450, 2017

    2017

  77. [85]

    The geometry of the gibbs measure of pure spheri cal spin glasses

    E Subag. The geometry of the gibbs measure of pure spheri cal spin glasses. Inventiones Mathematicae, 210:135 – 209, 2017

    2017

  78. [86]

    Following the ground states of full-rsb spheri cal spin glasses

    E Subag. Following the ground states of full-rsb spheri cal spin glasses. Comm. Pure Appl. Math. , 74:1021–1044, 2021

    2021

  79. [87]

    Free energy landscapes in spherical spin glass es

    E Subag. Free energy landscapes in spherical spin glass es. Duke Math. J. , 173:1291 – 1357, 2024

    2024

  80. [88]

    Talagrand

    M. Talagrand. Rigorous results for the Hopfield models w ith many patterns. Prob. Theor. Rel. Fields , 110:109–176, 1998

    1998

  81. [89]

    Talagrand

    M. Talagrand. The Parisi formula. Annals of mathematics , 163(2):221–263, 2006

    2006

  82. [90]

    Talagrand

    M. Talagrand. Mean field models and spin glasse: Volume II . A series of modern surveys in mathematics 55, Springer-Verlag, Berlin Heidelberg, 2011

    2011

  83. [91]

    Talagrand

    M. Talagrand. Mean field models and spin glasses: Volume I . A series of modern surveys in mathematics 54, Springer-Verlag, Berlin Heidelberg, 2011

    2011

  84. [92]

    J. Y. Zhao. The Hopfield model with superlinearly many pa tterns. 2011. available online at http:// arxiv.org/abs/1108.4771. 25

    2011 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.