A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy

Mihailo Stojnic

REVIEW 4 major objections 4 minor 1 cited by

A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy

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

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

Pith's one-line read The paper shows that a simple barrier-descent routine reaches about 0.76 of the Sherrington–Kirkpatrick ground-state free energy at n≈2000–8000, approaching the 0.763 thermodynamic limit.

desk verdict Useful heuristic with plausible numbers, but the theory is a heuristic too and the 'typically easy' claim overshoots the evidence. read the letter →

arxiv 2507.09247 v1 pith:OIIKNLUD submitted 2025-07-12 cond-mat.dis-nn cs.ITmath.ITmath.OCstat.ML

Mihailo Stojnic This is my paper · ORCID

classification cond-mat.dis-nncs.ITmath.ITmath.OCstat.ML MSC 82D3082B4468Q2590C26 PACS 75.10.Nr

keywords Sherrington–KirkpatrickmodelgroundstatefreeenergyCLuPalgorithmspinglassrandomdualitytheorybarrierdescentquadraticmaximizationtypical-casecomplexity

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 tries to establish that the ground-state free energy of the Sherrington–Kirkpatrick (SK) spin glass, an indefinite Gaussian quadratic maximization over the binary cube, is typically easy to approximate in practice despite being NP-hard in the worst case. It introduces a Controlled Loosening-up (CLuP) algorithm, a barrier-descent routine that gradually relaxes a temperature-like parameter while descending, and shows numerically that it reaches about 0.76 for n in the low thousands, close to the exact thermodynamic limit of roughly 0.763. The same theory characterizes the landscape in terms of a one-dimensional radius variable, explaining why plain gradient descent does not get trapped. If the claims hold, the practical computational gap for the SK ground-state problem is effectively erased.

What carries the argument

The load-bearing object is the one-dimensional surrogate landscape f_b(r_x)=-t_{0x}r_x-\log(-0.$9r_x^{2}$+\xi(r_x)+\kappa), where ξ(r_x) is the asymptotic maximum of x^T G x over the sphere-and-box set X(r_x)=\{x:\|x\|_2=r_x,\ $x_i^{2}$\le 1/n\}. The paper computes ξ(r_x) through fully lifted random duality theory, a stationarized duality method for random processes, giving the sequence 0.7979 to 0.7653 to 0.7640 as the lifting level increases. The CLuP-SK iteration is gradient descent on the barrier objective \bar{f}_{b,x}(x;t_{0x})=-t_{0x}\|x\|^2-\log\left(-\left(x^T\left(0.9I-\frac{G^T+G}{2\sqrt{2n}}\right)x-\kappa\right)\right)-\frac{1}{n}\sum_i\log(1-$nx_i^{2}$), with t_{0x} multiplied by 1.1 after each pass. The surrogate has no non-global local minima for the tested t_{0x} values, which is what makes plain descent work.

What would settle it

Take fresh Gaussian matrices of size n=$10^{5}$, run the published CLuP-SK dynamics with the stated parameters (one random start, no restarts), and record the best normalized objective. If the value stays below 0.75 or varies widely across starts, the surrogate-landscape assumption and the claimed typical easiness would be contradicted; movement toward 0.763 with increasing n would confirm them.

Watch

Extended reading notes

Core claim

The central claim is that a simple iterative procedure can erase the residual constant-factor computational gap of the SK model in the typical case. Concretely, running CLuP-SK on Gaussian instances with n=2000, 4000, and 8000 gives normalized ground-state free energies of 0.755, 0.757, and 0.758, respectively, and the paper's fully lifted random duality theory yields the n→∞ limit 0.763, in agreement with established values of about 0.7632. The algorithm requires no precomputed order-parameter function, in contrast to earlier polynomial-time message-passing schemes that depend on Parisi parameters. The argument ties algorithmic success to a surrogate loss landscape along the radius r_x that exhibits no non-global local minima for the CLuP-SK model and its trimmed variant.

Load-bearing premise

The load-bearing premise is that the random objective x^T G x inside the barrier can be replaced by its deterministic large-n maximum ξ(r_x) uniformly across every radius level X(r_x), so the one-dimensional surrogate faithfully represents the true high-dimensional landscape; if that concentration fails, plain gradient descent could stall in local minima even at large n.

Editorial extensions

If this is right

At n=2000, 4000, and 8000, single runs of plain gradient descent on the CLuP-SK barrier reach normalized ground-state free energies of approximately 0.755, 0.757, and 0.758, converging toward the theoretical 0.763 limit.
The associated CLuP-SK model's ground-state free energy ξ(r_x), viewed as a function of the radius r_x, is monotone increasing and has no non-global local optima at the lifting levels tested, which is why descent-based optimization succeeds.
Higher lifting levels refine the theoretical prediction from 0.7979 through 0.7653 and 0.7640 toward the known 0.7632 value, and the simulated overlap distribution matches the predicted RSB q(c/c_2) distribution on the fifth partial level.
No precomputed Parisi or order-parameter function is needed to run the algorithm, in contrast to earlier polynomial-time message-passing schemes.
Near-optimal configurations produced by CLuP-SK display an ultrametric overlap structure consistent with replica symmetry breaking predictions.

Reading between the lines

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

A testable consequence the paper leaves implicit is that if the surrogate landscape remains unimodal as t_{0x}→∞, the residual gap between simulated values (0.758 at n=8000) and the 0.763 limit should close uniformly as n grows.
The same CLuP-style loosening could plausibly transfer to other random quadratic maximization problems with sphere-and-box feasible sets, such as Hopfield-type or p-spin models, since the paper's construction is not tied to the specific SK interaction matrix beyond the Gaussian assumption.
If typical-case SK is genuinely easy for this procedure, worst-case NP-hardness results cease to be predictive for Gaussian instances, and similar barrier-descent methods may erode computational gaps in other random problems where uniform concentration holds.
The overlap and ultrametricity plots suggest CLuP-SK can serve as a practical sampler of near-optimal spin configurations, potentially replacing replica-based calculations in finite-size studies.

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.

Desk Editor's Note

read the letter

Short version: this is a useful heuristic paper with a thin theory. The CLuP-SK algorithm is simple, parameter-light, and the reported numbers are plausible: 0.755/0.757/0.758 at n=2000/4000/8000, heading toward the known Parisi value around 0.763. What's new is that it gets there without precomputed Parisi parameters, which IAMP needs. The overlap/ultrametricity plots are a nice empirical bonus. The paper is honest about its caveats: it calls Section 4.2.1 an approximate landscape characterization and says other intrinsic features may matter. That honesty extends to a fair literature review, heavily self-referential but complete on the classical SK results.

The soft spots are exactly where you'd expect. Eq (61) replaces the random quadratic inside the barrier objective with its asymptotic maximum xi(rx) over X(rx). That kills the fluctuations that can create high-dimensional local minima, and it assumes the descent finds the maximizing x for each radius. The no-local-optima conclusion is about the one-dimensional profile, not the actual high-dimensional objective. The paper admits this, but the abstract's 'typically easy' claim is stronger than the evidence. Theorems 1 and 2 are imported from the author's own fl RDT papers without proof; a referee would need to verify those or the paper should mark the whole theoretical section heuristic. Numerical evidence needs work: no error bars, no code, no comparison against IAMP or other baselines, and Table 2 is three points. I don't think this is fatal; the core empirical claim is testable and likely correct in broad brush. But as written, the theory is a suggestion rather than a proof.

Who is this for? People who want a practical near-optimal solver for the SK model and are willing to trust an empirical demonstration. It is not a rigorous complexity-theoretic statement. The fl RDT framework users may also find the application interesting. I would send it to a serious referee—the algorithm is simple enough and the numbers good enough that the community benefits from an independent check—but the referee should insist on code, more experiments, and a clear separation between proved and heuristic claims.

Referee Report

4 major / 4 minor

Summary. The paper proposes CLuP-SK, a barrier-descent ("Controlled Loosening-up") algorithm for the Sherrington-Kirkpatrick ground-state problem, and reports that for n on the order of a few thousand it achieves ground-state free energy values around 0.75–0.76, close to the Parisi value 0.763. To analyze the algorithm, the author introduces a family of CLuP-SK random models and uses fully lifted random duality theory (fl RDT), from the author's earlier works, to compute the asymptotic ground-state energy ξ(r_x) as a function of the radius r_x. The paper then studies a one-dimensional barrier profile f_b(r_x), claims it has no non-global local optima, simulates the CLuP-SK dynamics for n = 200, 1000, 2000, 4000, 8000, and reports excellent agreement with the theoretical predictions. It also reports overlap distributions and an ultrametric Gram matrix for near-optimal configurations.

Significance. If the central claims were fully supported, this would be a practically significant result: a simple barrier method would approach the SK ground-state energy without requiring precomputed Parisi parameters, in contrast to IAMP-type methods. The reported numerical agreement between the simulated dynamics and the theoretical curves (Figures 5–13) is visually convincing, and the emergence of ultrametric structure in Figure 15 is striking. The paper also makes a useful conceptual connection between a CLuP-type algorithm and a random-model analysis. However, the significance is conditional: the theoretical machinery is imported from the author's own arXiv preprints without proofs, the landscape analysis is carried out for a one-dimensional surrogate rather than the true high-dimensional objective, and the manuscript contains no concentration result for the key replacement of a random quadratic form by its asymptotic maximum. These gaps are load-bearing for the claim that computing the SK near-ground-state free energy is "typically easy."

major comments (4)

[Section 3, Theorems 1 and 2] The theoretical predictions rest on Theorem 1, which is quoted from the author's own preprint [98] with the proof deferred to "line-by-line derivations" in [94,97,98], and on Theorem 2, whose proof states that it "follows automatically." The manuscript does not state or verify the "complete sfl RDT frame" assumptions needed for the exact equality in Eq. (21). Since Eqs. (35)–(36) and Table 1 all depend on this equality, the theory is not self-contained and cannot be independently checked from the manuscript. Moreover, because the same unproven framework is used both to predict and to interpret the simulations, the reported "excellent agreement" does not independently validate either the theory or the algorithm. I recommend either including a complete proof, or precisely stating the conditions under which Eq. (21) holds and pointing to accessible peer-reviewed versions of [94,97,98].
[Section 4.2.1, Eq. (61)] The replacement of the random quadratic form x^T G x by the deterministic quantity ξ(r_x) is not justified. The barrier objective in Eq. (59) depends, for a fixed instance G, on the maximum of the random quadratic form over X(r_x), whereas ξ(r_x) is defined in Eq. (14) as a thermodynamic-limit expectation of that maximum. The paper provides no concentration bound showing that sup_{x∈X(r_x)} x^T G x / √(2n) is close to ξ(r_x) with high probability, nor any finite-n fluctuation estimate. Because this substitution is the basis for the one-dimensional profile f_b(r_x) in Eq. (61) and for the no-local-optima conclusion, the absence of a concentration argument is a load-bearing gap.
[Section 4.2.1 and 4.2.2] The no-local-optima claim is established only for the one-dimensional profile f_b(r_x), not for the high-dimensional objectives in Eqs. (56) and (64) on which gradient descent actually runs. A benign one-dimensional projection does not rule out spurious stationary points in directions orthogonal to r_x, and the paper itself acknowledges this by noting that "whether or not other intrinsic features beyond the loss landscape play much of an additional role remains to be seen" and that the numerical results in Section 4.2.2 "need to be taken with a bit of additional caution." These caveats are in tension with the abstract's conclusion that computing the SK near-ground-state free energy is "typically easy." Either the high-dimensional landscape needs to be characterized, or the strength of the concluding claim should be reduced to match the evidence.
[Section 4.1, Eq. (55)] The algorithm as specified in Eq. (55)–(56) lacks a step-size rule, a stopping criterion, and any complexity estimate; the text says only that the parameters κ, t_0x, and c(t) are "fairly flexible." For the central claim that the problem is "typically easy," a statement about the number of iterations or total floating-point operations is needed, or at least a clear reformulation of the claim as a purely empirical finite-n observation. As written, the reader cannot tell whether the reported n ≤ 8000 runs are representative or whether the procedure is guaranteed to terminate in polynomial time.

minor comments (4)

[Abstract and Conclusion] There are typos such as "agrement" and inconsistent spacing in "ﬂ RDT"; these should be corrected.
[Section 3.2, Eq. (39)] The displayed formulas for f^{(1)}_{q,1} and f^{(1)}_{q,2} are difficult to parse, with ambiguous parentheses and expressions like "2/2/γ"; please rewrite them in a cleaner form and verify all prefactors.
[Figure 15 and Table 3] Figure 15 has no caption explaining what is plotted, and Table 3 intermixes "partial" and "full" rows without a clear ordering; a short caption and consistent row labels would improve readability.
[References] Several core references, in particular [94], [97], and [98], are arXiv preprints with no publication status, and reference [101] is incomplete ("2025. available online at arxiv."). Please supply DOIs or journal information where available.

Circularity Check

1 steps flagged · score 4.0 of 10

Central theory chain is load-bearing on the author's own unproved fl RDT preprints, but the empirical 0.76 result and the Parisi-anchored 0.763 limit provide independent content.

self citation load bearing [Section 3, Theorem 1 (Eqs. (19)-(21)) and Theorem 2 (Eq. (36)); also abstract]
"Further connecting to recent random processes studies [94, 97], we characterize the models and CLuP-SK algorithm via fully lifted random duality theory (fl RDT) [98]. ... Proof. Follows after repeating line-by-line derivations in [94, 97, 98] with cosmetic change x → rx and trivial y → x, y → x, and bk → ck symmetry adjustments."

The headline theoretical prediction ξ(1) ≈ 0.763 (Table 2, '∞ (theory)') and the ξ(rx) curves used in the landscape analysis (Eq. (61)) are computed from Theorem 2, whose proof is not given here but deferred to the same author's preprints [94,97,98]. Those preprints are not machine-checked or independently published, so the derivation chain for the 'theory' terminates in a self-citation whose content is assumed rather than established. The paper then presents simulation/theory agreement as validation, but the theory side of that agreement is the self-cited fl RDT framework, so the agreement does not independently verify the framework. Eq.

full rationale

The central empirical claim (CLuP-SK reaches ~0.76 for n ≈ 2000-8000, Table 2) is a direct simulation result and is not forced by any fitted parameter: κ = 0.155 is fixed across experiments, and the limiting value 0.763 is also independently known from Parisi RSB theory (citations [30,66,67]), so the numerical achievement has an external anchor. The 1D surrogate landscape in Eq. (61) is an approximation; the paper itself labels Section 4.2.1 an 'approximate landscape characterization' and says the numerically based results 'need to be taken with a bit of additional caution,' while Section 4.2.1 also states 'Whether or not other intrinsic features beyond the loss landscape play much of an additional role remains to be seen.' The gap between no-local-optima for the rx-profile and the true high-dimensional barrier objective is a correctness risk, not a circular reduction. The main circularity concern is the load-bearing deferral of Theorem 1/2 to the author's own fl RDT preprints [94,97,98]; because the theorem is not proved or machine-checked here, the 'theoretical predictions' against which simulations are validated rest on an unverified self-citation. However, since the algorithm's measured performance and the known Parisi value provide independent content, the paper is only partially circular, not fully reducible to its inputs.

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

The central claim rests on a small number of hand-picked algorithmic parameters (κ, initial t0x, schedule increment) and on several unproven or self-cited theoretical assumptions, most notably the fl RDT strong duality theorem and the concentration/representation assumption for the landscape. No new physical or mathematical entities are introduced.

free parameters (3)

κ (barrier offset) = 0.155
Chosen by hand in all experiments; the algorithm's search path and final value depend on it. The paper states 'κ is a free parameter' in Section 4.1.
initial schedule t0x^0 = 0.0005
Starting value for the barrier schedule; chosen arbitrarily and changed as n varies.
schedule increment c(t) = 1.1
Geometric growth factor for t0x; chosen as a 'solid starting choice' without systematic tuning.

assumptions (4)

ad hoc to paper fl RDT strong sfl random duality (Theorem 1) holds for the CLuP-SK model
Imported from the author's own prior works (references 94, 97, 98) without proof in this paper. All the theoretical predictions in Section 3 depend on it.
domain assumption The random quadratic form x^T G x concentrates to its maximum ξ(rx) over X(rx), enabling the replacement in landscape equation (61)
Equation (61) replaces the random expression with its deterministic surrogate; no concentration bound is provided.
domain assumption The surrogate one-dimensional landscape fb(rx) correctly reflects the high-dimensional objective's lack of bad local minima; beyond the first and second lifting levels, no higher-order barriers are checked
The paper acknowledges OGP and local entropy could matter but doesn't rule them out; the landscape analysis is only carried out for r = 1 and r = 2 (and partially r = 3).
ad hoc to paper The 'modulo-m sfl' results from references 94, 97, 98 are equivalent to the full sfl results
The paper states numerical evaluations were conducted relying on 'modulo-m sfl results' and obtained the same results, but no proof is given.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy." pith.science (2026). https://pith.science/paper/OIIKNLUD

@misc{pith2026250709247,
  author       = {Pith},
  title        = {Pith review of: A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OIIKNLUD}},
  note         = {Machine review of arXiv:2507.09247}
}

abstract

We consider algorithmic determination of the $n$-dimensional Sherrington-Kirkpatrick (SK) spin glass model ground state free energy. It corresponds to a binary maximization of an indefinite quadratic form and under the \emph{worst case} principles of the classical NP complexity theory it is hard to approximate within a $\log(n)^{const.}$ factor. On the other hand, the SK's random nature allows (polynomial) spectral methods to \emph{typically} approach the optimum within a constant factor. Naturally one is left with the fundamental question: can the residual (constant) \emph{computational gap} be erased? Following the success of \emph{Controlled Loosening-up} (CLuP) algorithms in planted models, we here devise a simple practical CLuP-SK algorithmic procedure for (non-planted) SK models. To analyze the \emph{typical} success of the algorithm we associate to it (random) CLuP-SK models. Further connecting to recent random processes studies [94,97], we characterize the models and CLuP-SK algorithm via fully lifted random duality theory (fl RDT) [98]. Moreover, running the algorithm we demonstrate that its performance is in an excellent agrement with theoretical predictions. In particular, already for $n$ on the order of a few thousands CLuP-SK achieves $\sim 0.76$ ground state free energy and remarkably closely approaches theoretical $n\rightarrow\infty$ limit $\approx 0.763$. For all practical purposes, this renders computing SK model's near ground state free energy as a \emph{typically} easy problem.

Figures

Figures reproduced from arXiv: 2507.09247 by the authors.

**Figure 1.** ξ as a function of rx r. Mimicking the above procedures, one has −ψ¯ (r) rd (q, c, γ, rx) = − 1 2 Xr+1 k=2 (q 2 k−1 − q 2 k )ck + γr3 x + f (r) q , (52) where f (r) q = 1 cr EUr+1 log  EUr [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗

**Figure 2.** fb(rx) t0x as a function of rx; t0x = 1 with function fb,1 x;t¯ (t) 0x specified by an argument t¯ (t) 0x fb,1 x;t¯ (t) 0x = t¯ (t) 0x −t0xkxk2 − log − x T 0.9I − 1 2 √ 2n [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

**Figure 3.** fb(rx) t0x as a function of rx; t0x = 3 caution). To that end, for fixed rx (0 < rx ≤ 1) and r¯x we introduce the following CLuP-SK model: max x∈X¯(rx,r¯x) x T Gx, (65) with X¯(rx, r¯x) , ( x|x ∈ R n , kxk2 = rx, 1 n Xn i=1 log 1 − nx 2 i = ¯rx ) . (66) Analogously to (11)-(12) we define corresponding Hamiltonian and partition function H¯ csk(G) = X x∈X¯(rx,r¯x) x T Gx, (67) and Z¯ csk(β, G) = X x∈X¯(rx,r¯x) e βH¯… view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: fb(rx) t0x as a function of rx; t0x = 5 now have analogously to (71) ¯ξ(rx, r¯x) = ¯fcsk(∞) = limn→∞ EG maxx∈X¯(rxr¯x) x TGx √ 2n = − 1 √ 2 limn→∞ ψrd,1(qˆ, ˆc, rx, r¯x), (71) where following (23) and (25) ψrd,1(q, c, rx, r¯x) = 1 2 Xr+1 k=2 q 2 k−1 − q 2 k ! ck − 1 n …

**Figure 5.** Figure 5: fb(ˆrx) t0x as a function of t0x From (72)-(76) limn→∞ ψrd,1(qˆ, ˆc, rx, r¯x) = ψ¯ rd,1(qˆ, cˆ, γ, ˆ ν, r ˆ x, r¯x), (77) where ψ¯ rd,1(q, c, γsq , rx) = 1 2 Xr+1 k=2 q 2 k−1 − q 2 k ! ck − γr3 x − νrxr¯x − ϕ(D¯ (bin) 1 (ck(q)), c), (78) and analogously to (32) ϕ(D¯ (b…

**Figure 6.** Figure 6: ξ(ˆrx) as a function of t0x and after connecting (71) to (78) and (79) obtains ¯ξ(rx, r¯x) = ¯fcsk(∞) = limn→∞ EG maxx∈X¯(rx,r¯x) x T Gx √ 2n = − 1 √ 2 limn→∞ ψrd,1(qˆ, cˆ, rx, r¯x) = − 1 √ 2 ψ¯ rd,1(qˆ, ˆc, γ, ˆ ν, r ˆ x, r¯x) = 1 √ 2 [PITH_FULL_IMAGE:figures/full_fi…

**Figure 7.** Figure 7: rˆx as a function of t0x For a fixed t0x we are interested in behavior of ¯fb (rx, r¯x) = min x∈X¯(rx,r¯x) −t0xkxk2 − log − x T 0.9I − 1 2 √ 2n [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]

**Figure 8.** Figure 8: f¯b(rx) t0x as a function of rx; t0x = 20 – CLuP-SK model CLuP-SK for n = 200, n = 1000, and n = 2000. As can be seen from figures, even though the dimensions are fairly small (compared to n → ∞), the agreement between theoretical and simulated results is excellent. t0…

**Figure 9.** Figure 9: f¯b(ˆrx) t0x as a function of t0x – CLuP-SK model In Figures 12 and 13 we show the effect that changing the underlying dimension n has on ¯ξ(ˆrx). Increasing n from a few tens and hundreds to a few thousands we observe at what pace the simulated CLuP-SK dynamics approa…

**Figure 10.** Figure 10: ¯ξ(ˆrx) as a function of t0x – CLuP-SK model parts of the Gibbs measure associated with the overlaps concentrate on q2, q3, . . . , qr. In [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]

**Figure 11.** Figure 11: rˆx as a function of t0x – CLuP-SK model [PITH_FULL_IMAGE:figures/full_fig_p022_11.png]

**Figure 12.** Figure 12: Convergence of ¯ξ(ˆrx) as n grows – CLuP-SK model discuss them in separate papers. References [1] E. Abbe, S. Li, and A. Sly. Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron. In 62nd IEEE Annual Symposium on Foundations of Computer …

**Figure 13.** Figure 13: Convergence of limt0x→∞ ¯ξ(ˆrx) as n grows -D- CLuP-SK model [10] D. J. Aldous. The zeta(2) limit in the random assignment problem. Random Structures Algorithms, 18:381–418, 2001. [11] S. E. Alm and G. B. Sorkin. Exact expectations and distributions for the random ass…

**Figure 14.** Figure 14: q as a function of c c2 [21] A. S. Bandeira, D. Kunisky, and A. S. Wein. Computational hardness of certifying bounds on constrained PCA problems. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA,…

**Figure 15.** Figure 15: SK-model - Gram matrix of overlaps near the optimu [PITH_FULL_IMAGE:figures/full_fig_p026_15.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

CLuP practically achieves $\sim 1.77$ positive and $\sim 0.33$ negative Hopfield model ground state free energy
cond-mat.dis-nn 2025-07 conditional novelty 6.0 of 10

CLuP±Hop approximates Hopfield ground state free energies to within about 0.3% using simple gradient descent, backed by the author's fully lifted random duality theory.

Reference graph

Works this paper leans on

115 extracted references · 41 canonical work pages · cited by 1 Pith paper

[98]

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

arXiv 2023
[1]

E. Abbe, S. Li, and A. Sly. Proof of the contiguity conject ure and lognormal limit for the symmetric perceptron. In 62nd IEEE Annual Symposium on Foundations of Computer Scienc e, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 327–338. IEEE, 2021

2021
[2]

E. Abbe, S. Li, and A. Sly. Binary perceptron: eﬃcient alg orithms can ﬁnd solutions in a rare well- connected cluster. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computi ng, Rome, Italy, June 20 - 24, 2022 , pages 860–873. ACM, 2022

2022
[3]

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
[4]

Achlioptas and Y

D. Achlioptas and Y. Peres. The threshold for random k-SA T is 2klnk −O(k). Journal of the AMS , 17:947–973, 2004

2004
[5]

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
[6]

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
[7]

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

2025

Show all 115 references

[8]

A. E. Alaoui and M. Sellke. Algorithmic pure states for th e negative spherical perceptron. Journal of Statistical Physics, 189(27), 2022

2022
[9]

D. J. Aldous. Asymptotics in the random assignment probl em. Probab Theory Related Fields , 93:507– 534, 1992. 23 n 101 102 103 104 105 limt0x→∞ ¯ξ(ˆrx) 0.64 0.66 0.68 0.7 0.72 0.74 0.76 Convergence of limt0x→∞ ¯ξ(ˆrx) as n grows limt0x,n→∞ ¯ξ(ˆrx) ≈ 0.7632 – theory ( ∞-sﬂ RDT...

1992
[10]

D. J. Aldous. The zeta(2) limit in the random assignment problem. Random Structures Algorithms , 18:381–418, 2001

2001
[11]

S. E. Alm and G. B. Sorkin. Exact expectations and distri butions for the random assignment problem. Combinat. Probab. Comput. , 11(3):217–248, 2002

2002
[12]

Arora, E

S. Arora, E. Berger, E. Hazan, G. Kindler, and M. Safra. O n non-approximability for quadratic programs. 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

2005
[13]

Aubin, W

B. Aubin, W. Perkins, and L. Zdeborova. Storage capacit y in symmetric binary perceptrons. J. Phys. A, 52(29):294003, 2019

2019
[14]

Auﬃnger and W.-K

A. Auﬃnger and W.-K. Chen. The Parisi formula has a uniqu e minimizer. Communications in Mathematical Physics, 335(3), 2015

2015
[15]

Auﬃnger, W.-K

A. Auﬃnger, W.-K. Chen, and Q. Zheng. The SK model is inﬁn ite step replica symmetry breaking at zero temperature. Comm. Pure Appl. Math. , 73, 2020

2020
[16]

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
[17]

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
[18]

Baldassi, E

C. Baldassi, E. M. Malatesta, G. Perugini, and R. Zecchi na. Typical and atypical solutions in non- convex neural networks with discrete and continuous weight s. 2023. available online at http://arxiv. org/abs/2304.13871

2023 arXiv
[19]

Baldassi, E

C. Baldassi, E. M. Malatesta, G. Perugini, and R. Zecchi na. Typical and atypical solutions in nonconvex neural networks with discrete and continuous weights. Phys. Rev. E , 108:024310, Aug 2023

2023
[20]

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. 24 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...

2020
[21]

A. S. Bandeira, D. Kunisky, and A. S. Wein. Computationa l hardness of certifying bounds on con- strained PCA problems. In 11th Innovations in Theoretical Computer Science Conferenc e, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA , volume 151 of LIPIcs, pages 78:1–...

2020
[22]

Bayati and A

M. Bayati and A. Montanari. The dynamics of message pass ing on dense graphs, with applications to compressed sensing. In IEEE International Symposium on Information Theory, ISIT 2010, June 13-18, 2010, Austin, Texas, USA, Proceedings , pages 1528–1532. IEEE, 2010

2010
[23]

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
[24]

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
[25]

Bolthausen

E. Bolthausen. An iterative construction of solutions of the TAP equations for the Sherrington- Kirkpatrick model. Math. Stat. Learn. , 325(1):333–366, 2014

2014
[26]

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
[27]

Coja-Oghlan

A. Coja-Oghlan. The asymptotic k-SAT threshold. Proceedings of the forty-ﬁfth annual ACM sympo- sium on theory of computing (STOC) , pages 804–813, 2014

2014
[28]

Coppersmith and G

D. Coppersmith and G. Sorkin. Constructive bounds and e xact expectations for the random assignment problem. Random Structures Algorithms , 15:113–144, 1999

1999
[29]

T. Cover. Geomretrical and statistical properties of s ystems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers , (EC-14):326–334, 1965

1965
[30]

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
[31]

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. 25 5 10 15 20 25 30 5 10 15 20 25 30 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1 Figure 15: SK-model - Gram matrix of ov...

2008
[32]

J. Ding, A. Sly, and N. Sun. Satisﬁability threshold for random regular NAE-SAT. Proceedings of the forty-sixth annual ACM symposium on theory of computing (STOC ), pages 814–822, 2015

2015
[33]

Ding and N

J. Ding and N. Sun. Capacity lower bound for the Ising per ceptron. STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 816–827, 2019

2019
[34]

D. Donoho. High-dimensional centrally symmetric poly topes with neighborlines proportional to di- mension. Disc. Comput. Geometry , 35(4):617–652, 2006

2006
[35]

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
[36]

Donoho and J

D. Donoho and J. Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal proce ssing. Phylosophical transactions of the royal society A: mathematical, physical and engineering sci ences, 367, November 2009

2009
[37]

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

2011
[38]

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

1975
[39]

Franz and G

S. Franz and G. Parisi. The simplest model of jamming. Journal of Physics A: Mathematical and Theoretical, 49(14):145001, 2016

2016
[40]

Franz, A

S. Franz, A. Sclocchi, and P. Urbani. Critical jammed ph ase of the linear perceptron. Phys. Rev. Lett. , 123(11):115702, 2019

2019
[41]

Frieze and N

A. Frieze and N. Wormald. Random k-Sat: a tight threshol d for moderately growing k. Combinatorica, 28:297–305, 2005. 26

2005
[42]

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
[43]

Gamarnik, E

D. Gamarnik, E. C. Kizildag, W. Perkins, and C. Xu. Algor ithms and barriers in the symmetric binary perceptron model. In 63rd IEEE Annual Symposium on Foundations of Computer Scienc e, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 576–587. IEEE, 2022

2022
[44]

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
[45]

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
[46]

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
[47]

E. Gardner. The space of interactions in neural network s models. J. Phys. A: Math. Gen. , 21:257–270, 1988

1988
[48]

Gardner and B

E. Gardner and B. Derrida. Optimal storage properties o f neural networks models. J. Phys. A: Math. Gen., 21:271–284, 1988

1988
[49]

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

2003
[50]

B. Huang. Capacity threshold for the ising perceptron. In 65th IEEE Annual Symposium on Foun- dations of Computer Science, FOCS 2024, Chicago, IL, USA, Oct ober 27-30, 2024 , pages 1126–1136. IEEE, 2024

2024
[51]

Huang and M

B. Huang and M. Sellke. Tight lipschitz hardness for opt imizing mean ﬁeld 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

2022
[52]

Jagannath and I

A. Jagannath and I. Tobasco. A dynamic programming appr oach to the Parisi functional. In Proceed- ings of the American Mathematical Society , volume 14, pages 3135–3150
[53]

Kabashima

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

Kirkpatrick and D

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

1978
[55]

Linusson and J

S. Linusson and J. Wastlund. A proof of Parisi’s conject ure on the random assignment problem. Probabil Theory Related Fields , 128(3):419–440, 2004

2004
[56]

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
[57]

Mertens, M

S. Mertens, M. Mezard, and R. Zecchina. Threshold value s of random K-SAT from the cavity method. Random Struct. Alg. , 28:340–373, 2006

2006
[58]

Mezard, T

M. Mezard, T. Mora, and R. Zecchina. Clustering of solut ions in the random satisﬁability problem. Physical Review Letters , 94:197204, 2005

2005
[59]

Mezard and G

M. Mezard and G. Parisi. On the solution of the random lin k matching problem. J Physique , 48:1451– 1459, 1987

1987
[60]

Mezard, G

M. Mezard, G. Parisi, and R. Zecchina. Analytic and algo rithmic solution of random satisﬁability problems. Science, 297:812–815, 2002

2002
[61]

M. Molloy. The freezing threshold for k-colourings of a random graph. Proceedings of the forty-third annual ACM symposium on theory of computing (STOC) , pages 921–930, 2012. 27

2012
[62]

Montanari

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

2019
[63]

Montanari and S

A. Montanari and S. Sen. Semideﬁnite programs on sparse random graphs and their application to community detection. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory o f Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 , pages 814–827. ACM, 2016

2016
[64]

C. Nair, B. Prabhakar, and M. Sharma. Proofs of the Paris i and Coppersmith-Sorkin random assign- ment conjectures. Random Structures and Algorithms , 27(4):413–444, 2005

2005
[65]

Nesterov

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

1997
[66]

Oppermann and M

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

2008
[67]

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
[68]

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 temper- ature. Phys. Rev. Lett. , 95(19):197203, Nov 2005

2005
[69]

Panchenko

D. Panchenko. A connection between the Ghirlanda-Guer ra identities and ultrametricity. The Annals of Probability, 38(1):327–347, 2010

2010
[70]

Panchenko

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

2010
[71]

Panchenko

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

2013
[72]

Panchenko

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

2013
[73]

Panchenko

D. Panchenko. On the replica symmetric solution of the l -sat model. Electronic Journal of Probability , 19, 2014

2014
[74]

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

1979
[75]

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

1980
[76]

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
[77]

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

1946
[78]

Perkins and C

W. Perkins and C. Xu. Frozen 1-RSB structure of the symme tric Ising perceptron. STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory o f Computing , pages 1579–1588, 2021

2021
[79]

M. J. Schmidt and R. Oppermann. Method for replica symme try breaking at and near t = 0 with application to the Sherrington-Kirkpatrick model. Phys. Rev. E , 77(6):061104, Jun 2008

2008
[80]

Shcherbina and B

M. Shcherbina and B. Tirozzi. Rigorous solution of the G ardner problem. Comm. on Math. Physics , (234):383–422, 2003

2003
[81]

Sherrington and S

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

1975
[82]

Sherrington and S

D. Sherrington and S. Kirkpatrick. 50 years of spin glas s theory. 2025. available online at http:// arxiv.org/abs/2505.24432. 28

2025
[83]

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

arXiv
[84]

M. Stojnic. Upper-bounding ℓ1-optimization weak thresholds. available online at http://arxiv.org/ abs/1303.7289

arXiv
[85]

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

arXiv
[86]

M. Stojnic. Another look at the Gardner problem. 2013. a vailable online at http://arxiv.org/abs/ 1306.3979

2013 arXiv
[87]

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

2013 arXiv
[88]

M. Stojnic. Negative spherical perceptron. 2013. avai lable online at http://arxiv.org/abs/1306. 3980

2013
[89]

M. Stojnic. Regularly random duality. 2013. available online at http://arxiv.org/abs/1303.7295

2013 arXiv
[90]

M. Stojnic. Fully bilinear generic and lifted random pr ocesses comparisons. 2016. available online at http://arxiv.org/abs/1612.08516

2016 arXiv
[91]

M. Stojnic. Generic and lifted probabilistic comparis ons – max replaces minmax. 2016. available online at http://arxiv.org/abs/1612.08506

2016 arXiv
[92]

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
[93]

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

2020 arXiv
[94]

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

2023 arXiv
[95]

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

2023 arXiv
[96]

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
[97]

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

2023 arXiv
[99]

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

2023 arXiv
[100]

M. Stojnic. Studying Hopﬁeld models via fully lifted r andom duality theory. 2023. available online at http://arxiv.org/abs/2312.00071

2023 arXiv
[101]

M. Stojnic. Rare dense solutions clusters in asymmetr ic binary perceptrons – local entropy via fully lifted RDT. 2025. available online at arxiv

2025
[102]

The complexity of spherical p-spin models - A s econd moment approach

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

2017
[103]

The geometry of the gibbs measure of pure spher ical spin glasses

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

2017
[104]

Following the ground states of full-rsb spher ical spin glasses

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

2021
[105]

Free energy landscapes in spherical spin glas ses

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

2024
[106]

Talagrand

M. Talagrand. An assignment problem at high temperatu re. Ann. Probab., 31(2):818–848, 2003

2003
[107]

Talagrand

M. Talagrand. The Generic Chaining . Springer-Verlag, 2005

2005
[108]

Talagrand

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

2006
[109]

Talagrand

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

2011
[110]

Talagrand

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

2011
[111]

Wastlund

J. Wastlund. An easy proof of the ζ(2) limit in the random assignment problem. Electronic Commu- nications in Probability , 14:1475, 2009

2009
[112]

Wastlund

J. Wastlund. Replica symmetry of the minimum matching . Annals of Mathematics , 175(3):1061–1091, 2012

2012
[113]

J. G. Wendel. A problem in geometric probablity. Mathematics Scandinavia, 11:109–111, 1962

1962
[114]

R. O. Winder. Single stage threshold logic. Switching circuit theory and logical design , pages 321–332, Sep. 1961. AIEE Special publications S-134

1961
[115]

R. O. Winder. Threshold logic. Ph. D. dissertation, Princetoin University, 1962. 30

1962

Pith tools

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

[1] [98]

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

arXiv 2023

[2] [1]

E. Abbe, S. Li, and A. Sly. Proof of the contiguity conject ure and lognormal limit for the symmetric perceptron. In 62nd IEEE Annual Symposium on Foundations of Computer Scienc e, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 327–338. IEEE, 2021

2021

[3] [2]

E. Abbe, S. Li, and A. Sly. Binary perceptron: eﬃcient alg orithms can ﬁnd solutions in a rare well- connected cluster. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computi ng, Rome, Italy, June 20 - 24, 2022 , pages 860–873. ACM, 2022

2022

[4] [3]

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

[5] [4]

Achlioptas and Y

D. Achlioptas and Y. Peres. The threshold for random k-SA T is 2klnk −O(k). Journal of the AMS , 17:947–973, 2004

2004

[6] [5]

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

[7] [6]

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

[8] [7]

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

2025