Pith. sign in

REVIEW 4 major objections 5 minor 118 references

A large deviation view of \emph{stationarized} fully lifted blirp interpolation

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

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

Pith's one-line read Under stationary overlap parameters, the stationarized fully lifted interpolation gives equal large-deviation limits at the original and decoupled ends.

desk verdict A transparent but heavily companion-dependent extension of the author's stationarized interpolation frame: Theorem 3 is honestly conditional on an unproved concentration assumption, and the proof imports a key theorem from an unpublished companion. read the letter →

arxiv 2506.19273 v1 pith:U42IN3MM submitted 2025-06-24 math.PR cs.ITmath.ITstat.ML

Mihailo Stojnic This is my paper · ORCID
classification math.PRcs.ITmath.ITstat.ML MSC 60F1060G1582B44
keywords largedeviationsbilinearlyindexedrandomprocessesfullyliftedinterpolationstationarizationdualitytheorylocalentropiescomputationalgapsGaussiancomparison
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

This paper extends the stationarized fully lifted interpolation machinery for bilinearly indexed random processes (blirps) to a large-deviation setting. It aims to show that, after stationarization, the interpolating process has the same large-deviation limit at the original coupled process ($t=1$) and at the decoupled, analytically simpler process ($t=0$), provided the overlap parameters follow a stationary path and concentrate. If this holds, large-deviation rate functions of the original random structure can be obtained from the decoupled endpoint, which matters because those rate functions encode atypical-solution clustering, local entropies, and features believed to drive computational gaps in hard random optimization problems. The paper derives the $p$- and $q$-derivative structure of the interpolating function at every lifting level and shows that the stationarity system (127) makes the total derivative vanish, yielding Theorem 3 and the equal-limit statement (128).

What carries the argument

The central object is the $r$-level interpolating function $\psi(t)$, and its stationarized variant $\psi_1(t)$, attached to a bilinearly indexed random process (blirp): a random process indexed by pairs $(x^{(i_1)},y^{(i_2)})$ through a Gaussian matrix $G$, with a hierarchy of nested expectation powers governed by parameters $m=(m_1,\ldots,m_r)$, $p=(p_0,\ldots,p_{r+1})$, and $q=(q_0,\ldots,q_{r+1})$. The argument is carried by the derivative computations with respect to $p_{k_1}$ and $q_{k_1}$: Gaussian integration by parts rewrites every derivative as an overlap correlation averaged against reweighted measures $\gamma^{(r)}_{01}, \gamma^{(r)}_{02}, \gamma^{(r)}_{1}, \gamma^{(r)}_{21}, \gamma^{(r)}_{22}$, organized by the operators $\Phi$. The stationarity system (127) sets these $p$-$q$ derivatives of $\psi_1$ to zero along the interpolation path; combined with the identity for $d\psi/dt$ from the companion paper, this forces the total derivative to vanish, which is what makes the two endpoint limits equal.

What would settle it

Find a concrete equal-magnitude instance of the bilinear setup where (127) has a stationary solution but the two limits in (128) are different, or exhibit a standard model (for instance a perceptron) where no concentrating solution of (127) exists, which would show the theorem's hypothesis is not satisfiable in a case the paper presents as an application.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3: in the stationarized fully lifted large-deviation random duality frame, with equal-magnitude elements in $X$ and $Y$, the stationarity system (127) implies $\frac{d}{dt}\psi_1(\bar p(t),\bar q(t),\bar m(t),t)=0$ and the equality of large-deviation limits $\lim_{n\to\infty}\psi_1(\bar p(t),\bar q(t),\bar m(t),t)=\lim_{n\to\infty}\psi_1(\bar p(0),\bar q(0),\bar m(0),0)=\lim_{n\to\infty}\psi_1(\bar p(1),\bar q(1),\bar m(1),1)$. Here $\psi_1$ is the stationarized interpolating function built from $\psi$, $\bar p$ and $\bar q$ are the overlap parameters, and $\bar m$ the lifting parameters. The equality says that the hard original process and the decoupled one share the same large-deviation behavior once the stationarity conditions are met. The proof combines Gaussian integration by parts, the telescoping cancellation of the many correlation terms into the measures $\gamma^{(r)}$, and the companion paper's $t$-derivative identity, leaving only the stationarity conditions.

Load-bearing premise

The load-bearing premise is that stationary overlap parameters $\bar p(t), \bar q(t), \bar m(t)$ satisfying (127) exist, that the random overlaps concentrate around $\bar p(t)$ and $\bar q(t)$ (or the relevant $\phi$ terms vanish), and that all elements of $X$ and $Y$ have equal magnitudes; these are assumed, not proved.

Editorial extensions

If this is right

  • If the stationarity conditions hold, the large-deviation limit of the original bilinearly indexed process can be computed from the decoupled endpoint $t=0$, which is designed to be analytically tractable.
  • Corollary 1 gives explicit endpoint relations for unit-norm $X$ and $Y$, connecting $\psi_1$ at $t=0$ and $t=1$ with the split function $\psi_S$; these are ready-to-use formulas for applications.
  • Corollary 2 provides a lower bound, in the modulo-$m$ frame, on the large-deviation quantity at $t=1$ through an infimum over lifting parameters $m$ of decoupled quantities.
  • The stationarized frame now covers atypical features such as local entropies alongside typical behavior, extending the range of the earlier stationarized machinery.
  • The equal-limit identity upgrades the stationarized comparison theorem to large deviations, so the same interpolation path serves both typical and atypical analysis.

Reading between the lines

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

  • Editorial inference: the theorem is conditional on existence of a stationary path; for any concrete model the main task is verifying that (127) has a concentrating solution, and if it does not, the endpoint equality is not available.
  • Editorial inference: the equal-magnitude assumption is used to identify the measures $\gamma^{(r)}_2, \gamma^{(r)}_{21}, \gamma^{(r)}_{22}$. Relaxing it to a rotation-invariance or exchangeability condition is a natural testable extension, and the cancellations in (124)--(126) indicate where such a relaxation would need to hold.
  • Editorial inference: the pith suggests a general recipe---stationarize, then lift---for Gaussian-process large-deviation comparisons. A concrete numerical check on a perceptron or Hopfield model with known local-entropy behavior would show whether the stationarized endpoint reproduces the expected rate function.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. This paper develops a large-deviation version of the stationarized fully lifted bilinearly indexed random process (blirp) interpolation, complementing the large-deviation fully lifted framework of the companion paper [106] with a stationarized analogue of [103]. Section 2 computes the first-level p1 and q1 derivatives of the interpolation function, Section 3 extends these computations to an arbitrary lifting level r and records them in Theorem 1, and Section 4 imports the t-derivative formula as Theorem 2 from [106], defines a shifted function ψ1, and states Theorem 3. Theorem 3 asserts that if the stationarity system (127) admits a solution (p̄(t), q̄(t), m̄(t)) such that p̄ and q̄ are also concentration points of the relevant overlaps (or such that the quantities φ^(r) vanish), then the large-deviation limit of ψ1 is invariant along the interpolation path, so the limits at the decoupled endpoint t=0 and the original endpoint t=1 coincide. Corollaries 1 and 2 translate this invariance into relations involving the stationarized function ψS. The paper does not contain a concrete application; the advertised applications to local entropies and computational gaps are deferred to companion papers.

Significance. If Theorem 3 holds with its hypotheses satisfied, the paper would supply a stationarized large-deviation interpolation mechanism for atypical features of random structures, which could be a useful tool for local-entropy computations and for the analysis of computational gaps in random optimization problems. The algebraic organization is careful, and the paper is candid that the main invariance is conditional on the existence of stationarizing concentrated overlaps; that candor is a strength. However, as it stands the central theorem is a conditional statement whose premise is not instantiated on any concrete model, and the principal t-derivative identity used in its proof is imported from the companion paper [106] without proof. For these reasons, the current significance is programmatic rather than a completed result.

major comments (4)
  1. [Section 4, Theorem 3 and Eq. (127)] The stationarity system (127) consists of first-moment conditions; for example, for k1>1 the p_k1-derivative requires E_{γ^(r)_{k1+1}}[||x(i1)||^2 ||x(p1)||^2 (q_k1 ||y(i2)||^2 - (y(p2))^T y(i2))] = 0 up to the displayed prefactors. The proof of dψ1/dt = 0 in (129), however, requires the product fluctuation E[(p_k1 ||x||^2 - x^T x)(q_k1 ||y||^2 - y^T y)] under γ^(r)_{k1+1} to vanish, namely φ^(r)_{k1+1} = 0 in (117). That vanishing is not implied by the separate first-moment equations; it is a genuine concentration condition on the overlaps. Theorem 3 simply assumes the existence of p̄(t), q̄(t), m̄(t) satisfying both (127) and this concentration property, and no nontrivial model is provided where the assumption is verified. Thus the advertised invariance (128) is not established for any concrete random structure.
  2. [Section 4, Eq. (119) and Theorem 2] The t-derivative formula (119) is imported from the companion paper [106] with the proof omitted ("Proof. Presented in [106]."). This formula is the backbone of the final equality in (129): after the chain-rule terms vanish at the stationary point, dψ1/dt is reduced to the sum of the φ^(r) terms by applying (119). Because Theorem 3's central claim depends on this imported theorem, the present manuscript does not contain a complete proof of the invariance; it inherits Theorem 2 from a companion preprint. The authors should either include the proof or provide a precise, verifiable reference with a full identifier.
  3. [Section 3, Theorem 1 and Eqs. (36), (39), (42), (74), (96), (98), (110), (112)] Several load-bearing identities are stated as "analogous to [106]" or "determined in [106]" without derivation. For instance, the first-level identities (36), (39), and (42), and the higher-level identities (74), (96), (98), (110), and (112) are used to assemble the derivative formulas (83) in Theorem 1. The proof of Theorem 1 is therefore not self-contained: a reader cannot verify the central algebraic cancellations from the manuscript alone. This matters because Theorem 1 is the basis for the stationarity equations (127) on which Theorem 3 rests.
  4. [Introduction, Section 5, and Corollaries 1-2] The paper claims applicability to local entropies, computational gaps, perceptrons, and Hopfield models, but no concrete model instance is treated: no example is given where (127) is solvable and the concentration requirement of Theorem 3 is verified. Corollaries 1 and 2 inherit the conditional assumption of Theorem 3, so the stated applications are not yet supported by the manuscript. To make the claim substantive, the authors should either prove existence of stationarizing concentrated overlaps for at least one nontrivial random structure or explicitly recast the paper's contribution as a conditional framework whose hypotheses remain to be checked.
minor comments (5)
  1. [Section 4, Theorem 3] Theorem 3 contains the typo "stationirized" instead of "stationarized", and Eq. (128) has a doubled comma in ψ1(p̄(0), q̄(0), m̄(0),, 0).
  2. [Section 4, Corollary 1, Eq. (134)] Eq. (134) uses m̄_k(t) inside the sum, while the proof in (137) uses m̄_k(0); this appears to be a typo that should be corrected.
  3. [Section 2, around Eq. (1)] The text says "with repsect to" rather than "with respect to" in the paragraph introducing the expectation notation.
  4. [Proposition 1 and Theorem 1] The symbol p is used both as a scalar parameter in the definition of ψ(t) and as the vector p = [p0, p1, ...]; Proposition 1 states "scalars β, p, and s" while simultaneously using the vector p, which is confusing and should be disambiguated.
  5. [References] Reference [106] is cited as "available online at arxiv" without an arXiv identifier; since the manuscript relies heavily on [106], a full identifier would significantly aid verification.

Circularity Check

1 steps flagged · score 4.0 of 10

Central invariance theorem is conditional on stationarity/concentration and leans on a load-bearing same-author companion theorem; no definitional or fitted-parameter circularity.

  1. self citation load bearing [Section 4, Theorem 2 statement and proof (Eqs. (117)-(120)), used in Theorem 3 proof Eq. (129)]
    "We first recall on a fundamental result from [106]. Theorem 2. Assume the setup of Theorem 1. ... Then dψ(t)/dt = sign(s)β2/(2√n) (Σ_{k1=1}^{r+1} φ(r)_{k1} + φ(r)_{22} + φ(r)_{01} + φ(r)_{02}). It particular, choosing p0 = q0 = 1, one also has dψ(t)/dt = sign(s)β2/(2√n) (Σ_{k1=1}^{r+1} φ(r)_{k1} + φ(r)_{22}). Proof. Presented in [106]."

    The proof of Theorem 3's endpoint-invariance claim (128) depends on the derivative identity (120), which is stated as Theorem 2 and whose proof is entirely deferred to the author's companion paper [106] ('Proof. Presented in [106]'). In Eq. (129) the paper explicitly invokes (120) to conclude dψ1/dt = 0. Thus the central computation is load-bearing self-citation: the present paper supplies the stationarized function and stationarity system, but the decisive derivative relation is not independently established here or machine-checked. This is not a definitional equivalence - (127) is a stationarity assumption and (128) is a limiting equality - but it is the main non-independent link in the derivation chain.

full rationale

The paper's own contribution is the construction of ψ1 in (121), the stationarity system (127), and the conditional endpoint-invariance Theorem 3. The proof of Theorem 3 is not circular in the definitional sense: (127) is a stationarity condition, while (128) is a limiting equality obtained by the chain rule; the one does not literally restate the other. The main weakness is that the key derivative identity (119) is imported as Theorem 2 from the author's companion paper [106] with proof deferred ('Proof. Presented in [106]'), and the proof of Theorem 3 then leans on (120) in Eq. (129). That is a load-bearing self-citation, but the stationarization step and the explicit conditional statement give the claim independent content. No fitted parameter is relabeled as a prediction, and no equation is defined in terms of the target equality. The assumed existence of stationarizing concentrated overlaps is a correctness risk (unproved premise), not circularity. Accordingly score 4 rather than 0 or 6.

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

The derivation rests on standard Gaussian tools plus a substantial imported theorem from the author's own companion paper [106]. The most delicate input is the assumed existence of concentrated overlap parameters, which is exactly what makes the invariance identity (128) hold. No new physical entities are introduced.

assumptions (3)
  • standard math Gaussian integration by parts
    Used repeatedly throughout Sections 2 and 3 to compute expectations of products of Gaussian random variables, e.g., Eqs. (20), (29), (35), (38), (41).
  • domain assumption [106]'s Theorem 2
    Quoted in Section 4 as the fundamental derivative relation; the proof is deferred entirely to [106]. Theorem 3's proof relies on it directly.
  • ad hoc to paper Existence and concentration of stationarizing overlaps
    Theorem 3 assumes that p̄(t), q̄(t), and m̄(t) satisfy the stationarity system (127) and that p̄ and q̄ are also concentration points. No proof of existence is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A large deviation view of \emph{stationarized} fully lifted blirp interpolation." pith.science (2026). https://pith.science/paper/U42IN3MM

@misc{pith2026250619273,
  author       = {Pith},
  title        = {Pith review of: A large deviation view of \emphstationarized fully lifted blirp interpolation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U42IN3MM}},
  note         = {Machine review of arXiv:2506.19273}
}
read the original abstract

We consider \emph{bilinearly indexed random processes} (blirp) and study their interpolating comparative mechanisms. Generic introduction of the \emph{fully lifted} (fl) blirp interpolation in [105] was followed by a corresponding stationarization counterpart in [103]. A \emph{large deviation} upgrade of [105] introduced in companion paper [106] is complemented here with the corresponding one of [103]. Similarly to [106], the mechanism that we introduce extends the range of [103]'s applicability so that it encompasses random structures \emph{atypical} features. Among others these include the \emph{local entropies} (LE) which explain atypical solutions clusterings in hard random optimization problems believed to be directly responsible for the presumable existence of the so-called \emph{computational gaps}. Moreover (and similar to [105]), despite on occasion somewhat involved technical considerations, the final forms of the uncovered fundamental interpolating parameters relations are rather elegant and as such provide a valuable tool readily available for further use.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

118 extracted references · 55 canonical work pages

  1. [106]

    M. Stojnic. Fully lifted blirp interpolation – a large deviation view. 2025. available online at arxiv

    work page 2025

  2. [103]

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

    arXiv 2023

  3. [105]

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

    arXiv 2023

  4. [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 Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 327–338. IEEE, 2021

    2021

  5. [2]

    E. Abbe, S. Li, and A. Sly. Binary perceptron: efficient algorithms can find solutions in a rare well- connected cluster. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 860–873. ACM, 2022

    2022

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

  7. [4]

    Achlioptas and F

    D. Achlioptas and F. Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006 , pages 130–139. ACM, 2006

    2006

  8. [5]

    R. J. Adler. An introduction to Continuity, Extrema, and Related Topic for General Gaussian Pro- cesses. Institute of Mathematical Statistics, 1990

    1990

Show all 118 references
  1. [6]

    A. E. Alaoui, A. Montanari, and M. Sellke. Sampling from the 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, 2022 , pages 323–3...

    2022

  2. [7]

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

    2022

  3. [8]

    D. J. Altschuler. Critical window of the symmetric perceptron. 2022. available online at http: //arxiv.org/abs/2205.02319

    2022 arXiv

  4. [9]

    A. E. Alaoui amd D. Gamarnik. Hardness of sampling solutions from the symmetric binary perceptron

  5. [10]

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

    1985

  6. [11]

    Aubin, W

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

    2019

  7. [12]

    Baldassi, A

    C. Baldassi, A. Braunstein, N. Brunel, and R. Zecchina. Efficient supervised learning in networks with binary synapses. Proc. Natl. Acad. Sci. USA , 104(26):11079–11084, 2007

    2007

  8. [13]

    Baldassi, A

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

    2015

  9. [14]

    Baldassi, A

    C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, and 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

  10. [15]

    Baldassi, C

    C. Baldassi, C. Lauditi, E. M. Malatesta, G. Perugini, and R. Zecchina. Unveiling the structure of wide flat minima in neural networks. Phys. Rev. Lett., 127:278301, Dec 2021

    2021

  11. [16]

    Baldassi, E

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

    2023 arXiv

  12. [17]

    Baldassi, E

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

    2023

  13. [18]

    Baldassi, R

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

    2020

  14. [19]

    Baldi and S

    P. Baldi and S. Venkatesh. Number od stable points for spin-glasses and neural networks of higher orders. Phys. Rev. Letters, 58(9):913–916, Mar. 1987

    1987

  15. [20]

    A. S. Bandeira, A. El Alaoui, S. B. Hopkins, T. Schramm, A. S. Wein, and I. Zadik. The franz- parisi criterion and computational trade-offs in high dimensional statistics. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processi...

    2022

  16. [21]

    D. Barbier. How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states. 2024. available online at http://arxiv.org/abs/2408.04479

    2024 arXiv

  17. [22]

    Barbier, A

    D. Barbier, A. E. Alaoui, F. Krzakala, and L. Zdeborova. On the atypical solutions of the symmetric binary perceptron. Journal of Physics A: Mathematical and Theoretical , 57(19):195202, 2024

    2024

  18. [23]

    Barra, G

    A. Barra, G. Genovese, and F. Guerra. The replica symmetric approximation of the analogical neural network. J. Stat. Physics , July 2010

    2010

  19. [24]

    Barra, G

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

    2011

  20. [25]

    Barra, G

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

    2012

  21. [26]

    Bolthausen, S

    E. Bolthausen, S. Nakajima, N. Sun, and C. Xu. Gardner formula for Ising perceptron models at small densities. Proceedings of Thirty Fifth Conference on Learning Theory, PMLR , 178:1787–1911, 2022

    1911

  22. [27]

    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

  23. [28]

    Brunetti, G

    R. Brunetti, G. Parisi, and F. Ritort. Asymmetric Little spin glas model. Physical Review B , 46(9), September 1992

    1992

  24. [29]

    Cabasino, E

    S. Cabasino, E. Marinari, P. Paolucci, and G. Parisi. Eigenstates and limit cycles in the SK model. Journal of Physics A: Mathematical and General , 21:4201, 1988

    1988

  25. [30]

    S. H. Cameron. Tech-report 60-600. Proceedings of the bionics symposium, pages 197–212, 1960. Wright air development division, Dayton, Ohio

    1960

  26. [31]

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

    1965

  27. [32]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 73...

    2017

  28. [33]

    Ding and N

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

    2019

  29. [34]

    Feldman, W

    V. Feldman, W. Perkins, and S. S. Vempala. On the complexity of random satisfiability problems with planted solutions. SIAM J. Comput. , 47(4):1294–1338, 2018

    2018

  30. [35]

    Fernique

    X. Fernique. Des resultats nouveaux sur les processus Gaussiens. C.R. Acad. Sci. Paris Ser A-B , 278:A363–A365, 1974. 38

    1974

  31. [36]

    Fernique

    X. Fernique. Regularite des trajectoires des fonctions aleatoires Gaussiens. Springer Lecture notes , 480:1–96, 1975

    1975

  32. [37]

    Franz, S

    S. Franz, S. Hwang, and P. Urbani. Jamming in multilayer supervised learning models. Phys. Rev. Lett., 123(16):160602, 2019

    2019

  33. [38]

    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

  34. [39]

    Franz, G

    S. Franz, G. Parisi, M. Sevelev, P. Urbani, and F. Zamponi. Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems. SciPost Physics, 2:019, 2017

    2017

  35. [40]

    Franz, A

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

    2019

  36. [41]

    Franz, A

    S. Franz, A. Sclocchi, and P. Urbani. Surfing on minima of isostatic landscapes: avalanches and unjamming transition. SciPost Physics, 9:12, 2020

    2020

  37. [42]

    Gamarnik, A

    D. Gamarnik, A. Jagannath, and A. S. Wein. Low-degree hardness of random optimization problems. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 , pages 131–140. IEEE, 2020

    2020

  38. [43]

    Gamarnik, E

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

    2022

  39. [44]

    Gamarnik, C

    D. Gamarnik, C. Moore, and L. Zdeborova. Disordered systems insights on computational hardness. Journal of Statistical Mechanics: Theory and Experiment , (11):115015, 2022

    2022

  40. [45]

    Gamarnik and M

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

    2014

  41. [46]

    Gamarnik and M

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

    2017

  42. [47]

    Gamarnik and M

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

    2017

  43. [48]

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

    1988

  44. [49]

    Gardner and B

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

    1988

  45. [50]

    Y. Gordon. Some inequalities for Gaussian processes and applications. Israel Journal of Mathematics , 50(4):265–289, 1985

    1985

  46. [51]

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

    2003

  47. [52]

    Gutfreund and Y

    H. Gutfreund and Y. Stein. Capacity of neural networks with discrete synaptic couplings. J. Physics A: Math. Gen , 23:2613, 1990

    1990

  48. [53]

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

    1949

  49. [54]

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

    1982

  50. [55]

    S. B. Hopkins, P. K. Kothari, A. Potechin, P. Raghavendra, T. Schramm, and D. Steurer. The power of sum-of-squares for detecting hidden structures. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 720–7...

    2017

  51. [56]

    S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 20...

    2016

  52. [57]

    S. B. Hopkins, J. Shi, and D. Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 956–1006. JMLR....

    2015

  53. [58]

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

    2024

  54. [59]

    R. D. Joseph. The number of orthants in n-space instersected by an s-dimensional subspace. Tech. memo 8, project PARA, 1960. Cornel aeronautical lab., Buffalo, N.Y

    1960

  55. [60]

    J. P. Kahane. Une inegualite du type de Slepian et Gordon sur les processus Gaussiens. Israel Journal of Mathematics, 55(1):109–110, 1986

    1986

  56. [61]

    J. H. Kim and J. R. Roche. Covering cubes by random half cubes with applications to biniary neural networks. Journal of Computer and System Sciences , 56:223–252, 1998

    1998

  57. [62]

    Krauth and M

    W. Krauth and M. Mezard. Storage capacity of memory networks with binary couplings. J. Phys. France, 50:3057–3066, 1989

    1989

  58. [63]

    Ledoux and M

    M. Ledoux and M. Talagrand. Probability in Banach spaces: Isopermetry and Processes . Springer (New York), 1991

    1991

  59. [64]

    S. Li, T. Schramm, and K. Zhou. Discrepancy algorithms for the binary perceptron. 2024. available online at http://arxiv.org/abs/2408.00796

    2024 arXiv

  60. [65]

    M. A. Lifshits. Gaussian random functions . Kluwer, Boston, 1995

    1995

  61. [66]

    W. A. Little. The existence of persistent states in the brain. Math. Biosci., 19(1-2):101–120, 1974

    1974

  62. [67]

    Mezard, T

    M. Mezard, T. Mora, and R. Zecchina. Clustering of solutions in the random satisfiability problem. Physical Review Letters, 94:197204, 2005

    2005

  63. [68]

    Nakajima and N

    S. Nakajima and N. Sun. Sharp threshold sequence and universality for Ising perceptron models. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 638– 674, 2023

    2023

  64. [69]

    Panchenko

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

    2010

  65. [70]

    Panchenko

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

    2010

  66. [71]

    Panchenko

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

    2013

  67. [72]

    Panchenko

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

    2013

  68. [73]

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

    1979

  69. [74]

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

    1980

  70. [75]

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

    1980

  71. [76]

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

    1946

  72. [77]

    Pastur and A

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

    1978

  73. [78]

    Pastur, M

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

    1994

  74. [79]

    Perkins and C

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

    2021

  75. [80]

    Sah and M

    A. Sah and M. Sawhney. Distribution of the threshold for the symmetric perceptron. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2369–2382, 2023

    2023

  76. [81]

    Schlafli

    L. Schlafli. Gesammelte Mathematische AbhandLungen I. Basel, Switzerland: Verlag Birkhauser, 1950

    1950

  77. [82]

    Shcherbina and B

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

    1993

  78. [83]

    Shcherbina and B

    M. Shcherbina and B. Tirozzi. On the volume of the intrersection of a sphere with random half spaces. C. R. Acad. Sci. Paris. Ser I , (334):803–806, 2002

    2002

  79. [84]

    Shcherbina and B

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

    2003

  80. [85]

    Sherrington and S

    D. Sherrington and S. Kirkpatrick. Solvable model of a spin glass. Phys. Rev. Letters , 35:1792–1796, 1972

    1972

  81. [86]

    D. Slepian. The one sided barier problem for Gaussian noise. Bell System Tech. Journal , 41:463–501, 1962

    1962

  82. [87]

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

    arXiv

  83. [88]

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

    arXiv

  84. [89]

    M. Stojnic. Block-length dependent thresholds for ℓ2/ℓ1-optimization in block-sparse compressed sens- ing. ICASSP, IEEE International Conference on Acoustics, Signal and Speech Processing, pages 3918– 3921, 14-19 March 2010. Dallas, TX

    2010

  85. [90]

    M. Stojnic. ℓ1 optimization and its various thresholds in compressed sensing. ICASSP, IEEE Inter- national Conference on Acoustics, Signal and Speech Processing , pages 3910–3913, 14-19 March 2010. Dallas, TX

    2010

  86. [91]

    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

  87. [92]

    M. Stojnic. Towards improving ℓ1 optimization in compressed sensing. ICASSP, IEEE International Conference on Acoustics, Signal and Speech Processing , pages 3938–3941, 14-19 March 2010. Dallas, TX

    2010

  88. [93]

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

    2013 arXiv

  89. [94]

    M. Stojnic. Asymmetric Little model and its ground state energies. 2013. available online at http: //arxiv.org/abs/1306.3978

    2013 arXiv

  90. [95]

    M. Stojnic. Bounds on restricted isometry constants of random matrices. 2013. available online at http://arxiv.org/abs/1306.3779

    2013 arXiv

  91. [96]

    M. Stojnic. Discrete perceptrons. 2013. available online at http://arxiv.org/abs/1303.4375. 41

    2013 arXiv

  92. [97]

    M. Stojnic. Lifting ℓ1-optimization strong and sectional thresholds. 2013. available online at http: //arxiv.org/abs/1306.3770

    2013 arXiv

  93. [98]

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

    2013 arXiv

  94. [99]

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

    2013

  95. [100]

    M. Stojnic. Spherical perceptron as a storage memory with limited errors. 2013. available online at http://arxiv.org/abs/1306.3809

    2013 arXiv

  96. [101]

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

    2016 arXiv

  97. [102]

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

    2016 arXiv

  98. [104]

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

    2023 arXiv

  99. [107]

    V. N. Sudakov. Gaussian random processes and measures of solid angles in Hilbert space. Soviet Math. Dokl., 12(1):412–415, 1971

    1971

  100. [108]

    Talagrand

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

    1998

  101. [109]

    Talagrand

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

    2005

  102. [110]

    Talagrand

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

    2006

  103. [111]

    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

  104. [112]

    Venkatesh

    S. Venkatesh. Epsilon capacity of neural networks. Proc. Conf. on Neural Networks for Computing, Snowbird, UT, 1986

    1986

  105. [113]

    A. S. Wein. Average-case complexity of tensor decomposition for low-degree polynomials. In Proceed- ings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 1685–1698. ACM, 2023

    2023

  106. [114]

    J. G. Wendel. A problem in geometric probability. Mathematica Scandinavica, 1:109–111, 1962

    1962

  107. [115]

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

    1961

  108. [116]

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

    1962

  109. [117]

    C. Xu. Sharp threshold for the Ising perceptron model. Ann. Probab., 43(5):2399–2415, 2021. 42

    2021

  110. [2024]

    available online at http://arxiv.org/abs/2407.16627

    arXiv

Pith tools

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