Pith. sign in

REVIEW 4 major objections 6 minor 117 references

Fully lifted \emph{blirp} interpolation -- a large deviation view

T0 review · 4 major / 6 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 This paper claims that fully lifted interpolation extends into the large-deviation regime, yielding closed-form derivative identities that reach atypical features such as local entropy.

desk verdict The derivative identities are the real contribution; the local-entropy bridge (285) is asserted, not proved, and should block the advertised claim unless fixed. read the letter →

arxiv 2506.19272 v1 pith:MOTDJ6KX 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 largedeviationsinterpolationbilinearlyindexedrandomprocessesblirpliftinglocalentropybinaryperceptroncomputationalgaps
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 extends the fully lifted interpolation mechanism for bilinearly indexed random processes (blirps) from typical to atypical behavior by deriving an explicit formula for the derivative of the interpolation function in a large-deviation setting. If the formula is correct, comparing a complex bilinear random process with a decoupled linear counterpart reduces to evaluating averages over explicitly defined tilted measures, and the machinery automatically covers the same broad family of random structures as the earlier lifting framework. The proposed payoff is an analytic route to quantities such as the local entropy of rare, well-connected solution clusters in the binary perceptron, which are widely thought to bear on computational gaps. The paper states this payoff as a limit connecting the interpolation function to local entropy, while explicitly deferring the derivation of that limit to a companion paper.

What carries the argument

The central object is the interpolation function $\psi(t)$, which at $t=1$ is a Gaussian bilinearly indexed random process (a blirp) and at $t=0$ becomes two linearly indexed processes with norms replacing bilinear terms. The load-bearing computation is Gaussian integration by parts applied to the seven derivative terms grouped into $T_1$, $T_2$, and $T_G$; at each level of lifting, a telescoping scaling-and-cancellation leaves only the $\varphi$ averages. The tilted measures $\gamma^{(r)}$ are probability measures defined through nested expectation operators $\Phi_{U_k}$ and Gibbs weights, and they encode the entire dependence on the lifting level $r$, the parameter vectors $p$, $q$, $m$, the exponents $s$, $p$, and the interpolating time $t$.

What would settle it

Evaluate the right-hand side of (285) on finite binary perceptron instances: count solutions at a fixed overlap $\bar\delta$ for growing $n$, form the $n$-scaled logarithm, and check whether it approaches the asserted $\sigma(\bar\delta)$ from the interpolation side; any overlap where the two diverge while $\sigma(\bar\delta)$ is finite and nonzero would disprove the local-entropy connection.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: for any lifting level $r \geq 2$, the derivative of the fully lifted large-deviation interpolation function $\psi(t)$ equals $$\frac{d\psi(t)}{dt} = \frac{\operatorname{sign}(s)\$beta^{2}$}{2\sqrt{n}}\left(\sum_{k_1=1}^{r+1}\varphi_{k_1}^{(r)} + \varphi_{22}^{(r)} + \varphi_{01}^{(r)} + \varphi_{02}^{(r)}\right),$$ where the $\varphi$ terms are averages over the tilted measures $\gamma^{(r)}$, built from nested Gibbs expectations. These averages are closed-form expressions in norms and overlaps, such as $(p_{k_1-1}\|x\|\|x'\| - x^T x')$ multiplied by the analogous $q$-factor. Since $\psi(1)$ is the complicated bilinearly indexed process of interest and $\psi(0)$ is its simpler decoupled counterpart, the derivative formula turns the comparison into an integral of explicit expressions. The paper further claims that with a $\sqrt{n}$ scaling in the thermodynamic limit, the machinery reaches atypical features, including the local entropy $\sigma(\bar\delta)$ of the binary perceptron.

Load-bearing premise

The load-bearing premise is that the asserted simultaneous limit (285) holds: as $n$, $\beta$, and $p$ all go to infinity, $\psi(1)\sqrt{n}$ equals the binary perceptron's local entropy $\sigma(\bar\delta)$, which requires concentration to remove the Gaussian expectation and a $\sqrt{n}$ prefactor to extract the cluster exponent.

Editorial extensions

If this is right

  • For every random structure covered by the earlier lifting framework, the derivative identity provides a large-deviation comparison in closed form, making atypical as well as typical exponents accessible.
  • In the binary perceptron, the $\sqrt{n}$-scaled interpolation function is claimed to equal the local entropy $\sigma(\bar\delta)$, the exponential rate for the densest cluster at overlap $\bar\delta$, yielding an analytic handle on rare cluster structure below the capacity $\alpha_c \approx 0.833$.
  • The same machinery extends to symmetric binary perceptrons, Hopfield-type free-energy problems, and other optimal-objective settings where previously only typical behavior was analytically tractable.
  • When the stated concentration arguments apply, the Gaussian expectation in the thermodynamic limits can be removed, so the comparison holds at the level of deterministic limiting quantities.

Reading between the lines

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

  • Theorem 1's derivative formula is likely the reusable core: any statistical model that fits the blirp setup inherits a large-deviation comparison even before the local-entropy interpretation is needed.
  • A concrete next step not taken in the paper would be to test the $\varphi$-average formula numerically on small systems, comparing the integrated derivative against direct simulation of $\psi(1) - \psi(0)$.
  • If the local-entropy limit (285) is confirmed in the companion paper, the framework would give a rigorous route from interpolation to clustering exponents, potentially placing the local-entropy heuristic for computational gaps on a parameter-free footing.
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 / 6 minor

Summary. This paper extends the author's earlier fully lifted interpolation framework for bilinearly indexed random processes (blirps) from [104] to a large-deviation setting. It defines an interpolating function ψ(t) in (4) with normalized free-energy form, computes its derivative as a sum of expectations under tilted product Gibbs measures γ^(r), and packages the result as Theorem 1 (eq. (270)). The paper then claims in Section 5, via eq. (285), that a simultaneous limit n, β, p → ∞ of ψ(1)√n equals the binary perceptron local entropy σ(δ̄), and uses this claim to motivate potential applications to computational gaps and atypical random-structure features. The main technical content is the derivative computation; the local-entropy connection is asserted rather than derived and is deferred to a companion paper [105].

Significance. If Theorem 1 is correct, it is a substantial technical generalization of the interpolation machinery in [104] to large-deviation functionals, and it could provide a useful tool for studying atypical events in a broad class of bilinear random processes. The paper does not fit constants to data and the algebra is laid out in extenso, which aids verifiability. The advertised application to local entropy and computational gaps, however, rests entirely on the unproved limit (285); without that bridge the manuscript's contribution is a standalone derivative identity whose practical reach is not demonstrated. The paper also inherits a large part of its structure from the author's own prior work, which complicates independent verification but is not by itself a defect. Overall the significance is conditional: high if (285) can be established rigorously, moderate if the claims are re-scoped to the interpolation identity only.

major comments (4)
  1. [§5, eq. (285)] The central advertised application—connecting the large-deviation interpolation function to the binary perceptron local entropy—is asserted, not proved. The text states 'one then observes that' and 'It is not that difficult to see', but gives no derivation of the simultaneous limit n, β, p → ∞, no justification that the Gaussian expectation EG can be removed, no argument that the √n prefactor extracts the cluster exponent rather than diverging or vanishing, and no identification of the nested L_p/Rényi-type expression in ψ(1) with the finite-n count of overlap-constrained solutions. The paper explicitly defers details to the companion paper [105]. Because the abstract and introduction promise substantially wider applicability to atypical features such as local entropy and computational gaps, this unsupported limit is load-bearing. The paper should either prove (285) or explicitly re-scope its claims as conditional on [105].
  2. [Throughout; eqs. (1), (266), (285)] The symbol p is used both as a vector of lifting parameters p = [p_0, …, p_{r+1}] and as a scalar exponent appearing in the definition of ψ(t) and in the normalization 1/(p|s|√n m_r). This overloading is harmless in early sections but creates genuine ambiguity in eq. (285), where lim_{n,β,p→∞} refers to the scalar exponent while the vector p is still present in ψ(1). The simultaneous limit is therefore not well specified: it must be stated which parameters of the vector p are held fixed as the scalar p diverges. Please rename either the exponent or the vector.
  3. [§3.1.5, eq. (220) vs. §4, eq. (269)] There is an inconsistency between the second-level result stated in Proposition 2 and the general r-th level result in Theorem 1. In eq. (220), ϕ^(2)_02 is defined as (1 − p_0) E_{G,U_3} ⟨∥x(i1)∥_2^2 (q_0 ∥y(i2)∥_2 ∥y(p2)∥_2 − (y(p2))^T y(i2))⟩_{γ^(2)_02}, whereas the corresponding first-level quantity in (101) and the general r-level quantity in (269) both contain an additional factor (s − 1). As printed, Proposition 2 and Theorem 1 disagree for r = 2, so the derivative formula in (223) would differ from what Theorem 1 gives. This needs to be corrected.
  4. [§2.1.1 and §3.1.1, eqs. (25)-(26) and (122)-(123)] The final formula (270) is an average over the tilted measures γ^(r), so those measures must be probability measures. The paper verifies this only for γ^(1)_01 in eq. (26) and states that the proofs for the other γ's are identical and skipped. The omitted cases include the more complex product measures γ^(r)_22 and γ^(r)_{k_1+1} entering the main theorem. Since the validity of the theorem depends on the normalization of every γ, a short lemma covering all γ^(r) measures should be included rather than left to the reader.
minor comments (6)
  1. [§3.1.4, eq. (155)] There is a malformed subscript in the equation: the text 'γ(22_21' should presumably read 'γ^{(2)}_{21}'. Similar malformed subscripts appear elsewhere, e.g., the doubled expectation E_{G,U_2} E_{G,U_2} in eq. (99).
  2. [§2, eq. (4), and Proposition 1] Proposition 1 states p, β ≥ 0, but the definition of ψ(t) divides by p|s|√n m_1, so p = 0 is not admissible. Either state p > 0 or handle p = 0 as a separate limiting case.
  3. [§5, eqs. (281)-(282) and (285)] The notation for the function f in the interpolating process is not consistent: earlier definitions use f_{¯x(i3)}(x(i1)), while eqs. (281)-(282) write f_{x(i3)}(x(i1)) without the bar. This matters for the local-entropy interpretation of the constraint term.
  4. [Introduction and §5] There are numerous typos and stylistic errors, including 'a large deviation upgrade' in the abstract, 'majority od the existing approaches' and 'subsciprt' in Section 2, 'neureal networks' and 'predicated role' in Section 5, and 'instersected' in the reference list. A careful proofreading pass is needed.
  5. [References] Reference [105] is cited as 'available online at arxiv' without an arXiv identifier or any other locator, which makes it impossible for the reader to verify the claimed companion-paper results. Please provide the arXiv number.
  6. [Proof of Theorem 1, §4] The derivation for r ≥ 3 relies heavily on specific equations imported from [104] (e.g., equations (41), (52), (62), (71), (73), (174), (201), and (229)) without restating them. The statements are precise enough for a reader with [104] at hand, but a short appendix that lists the imported identities would substantially improve readability and verifiability.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: Theorem 1 is a genuine interpolation derivative identity; the only load-bearing gap is Section 5's deferred local-entropy bridge, which is missing support rather than circular.

full rationale

The paper's central mathematical result, Theorem 1 (Section 4, equations (266)-(270)), is obtained by differentiating the interpolating function ψ(t) and applying Gaussian integration by parts. The output φ terms are averages with respect to tilted measures γ(r) constructed from the same partition-function ingredients (Z_i3, C^(i1)_i3, and the Φ operators), so the identity is a calculation about the object it defines, not a restatement of an input. Nothing is fitted to data and no fitted parameter is relabeled as a prediction. The extensive use of [104] is citation of prior work with independent content: the paper repeatedly says it follows [104]'s equations, e.g., 'Following the strategy of [104]' and analogues of [104]'s (41), (52), (62), (71), (73), (174), (201), (229), and (249), but those are prior stated results, and the present paper also supplies the first- and second-level computations in Sections 2-3. The statement 'The proofs for other γ's are identical and we skip them' (Section 2.1.1, after (26)) is an omitted detail, not a circular step. The only genuinely load-bearing unsupported step is Section 5's equation (285), which asserts lim_{n,β,p→∞} ψ(1)√n = σ(δ̄) with the text 'It is not that difficult to see' and 'this avenue is pursued in companion paper [105] in full detail.' This bridges Theorem 1 to the advertised local-entropy and computational-gap applications, but it is not derived here. That is a missing-proof / correctness risk, not a circularity, because (285) is not an input to Theorem 1 and the paper does not define σ(δ̄) in terms of ψ's fitted parameters. Accordingly, no step reduces to its own input by construction; score 1 rather than 0 only to acknowledge the paper's very heavy reliance on the author's prior framework and the deferred [105] bridge for the headline application.

Assumptions & free parameters 5 free parameters · 5 assumptions · 2 invented entities

The paper is a pure mathematics derivation and introduces no fitted constants. The listed parameters are tunable parts of the interpolation machinery. The listed axioms capture where the paper leans on prior work ([104]) or on unproved limit assertions (285). The central added content is the derivative computation itself; everything about the claimed applications is carried by the local-entropy limit assumption and the perceptron embedding assumption.

free parameters (5)
  • lifting vectors p and q
    Partition the variances of the auxiliary Gaussian fields in the interpolation; not fitted to data, they are the tunable scales of the method, with special case p0 = q0 = 1 in (271).
  • lifting vector m = [m1,...,mr]
    Controls the nested expectation structure with m0 = 1 and mr+1 = 0; chosen by the analyst, not fitted.
  • large-deviation exponent p
    Scalar exponent in (1) and (102) that emphasizes atypical outcomes; the local-entropy application takes p → ∞ in (285), a limit not proved to commute with n and β.
  • replica-like exponent s and temperature β
    Interpolation parameters; s = -1 encodes feasibility for the spherical and binary perceptron per Section 5, and β is a temperature taken to infinity in (283)-(285).
  • overlap parameter δ̄
    Input to the local entropy σ(δ̄) in (285); selects the cluster overlap in the binary perceptron application.
assumptions (5)
  • standard math Gaussian integration by parts identity
    Used throughout Sections 2-4, e.g., equations (20), (30), (33), (65), and (79), to convert Gaussian expectations into derivative terms.
  • domain assumption The γ^{(r)} objects are valid probability measures
    The paper checks the sum-to-one property only for γ_{01}^{(1)} in equation (26) and states that proofs for the other measures are identical; the entire averaging notation ⟨·⟩_γ depends on this.
  • ad hoc to paper Structural identity with [104]'s computed terms
    Many steps import results from the author's prior paper [104] on the grounds that inner expectations are 'structurally identical,' e.g., 'From [104]'s (41) we have...' near equations (41)-(42) and again at (83), (86), (90), (201), and (229); any mismatch at higher lifting levels would break Theorem 1.
  • ad hoc to paper Assumed local-entropy limit (285)
    Section 5 asserts lim_{n,β,p→∞} ψ(1)√n = σ(δ̄) without proof, including concentration to remove EG and validity of the simultaneous limit; this is the bridge to the paper's claimed practical relevance.
  • domain assumption Perceptron embeddings into the blirp model
    Section 5 claims the binary and spherical perceptrons fit the model via specific choices of X, Y, s, and p in equations (283)-(285); the feasibility-model equivalence is standard but stated, not proved.
invented entities (2)
  • tilted product-Gibbs measures γ^{(r)} (γ_{01}, γ_{02}, γ_{1}, γ_{21}, γ_{22}, γ_{k})
    purpose: Weighting measures that absorb the expectations in the derivative identities (25), (122), and (248); all averages in Theorem 1 are taken with respect to them.
    Internal mathematical constructs introduced to compress the derivative formulas; they carry no external falsifiable handle, so they pose no graviton-type risk but also add no independent evidence.
  • fully lifted large-deviation interpolation function ψ with parameters [p, q, m, s, p, β]
    purpose: The central object whose derivative is computed in Propositions 1-2 and Theorem 1.
    A mathematical object generalizing [104]'s interpolation; its usefulness depends on the asserted (285) limit connecting it to local entropy, which is not proven here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully lifted \emph{blirp} interpolation -- a large deviation view." pith.science (2026). https://pith.science/paper/MOTDJ6KX

@misc{pith2026250619272,
  author       = {Pith},
  title        = {Pith review of: Fully lifted \emphblirp interpolation -- a large deviation view},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MOTDJ6KX}},
  note         = {Machine review of arXiv:2506.19272}
}
read the original abstract

[104] introduced a powerful \emph{fully lifted} (fl) statistical interpolating mechanism. It established a nested connection between blirps (bilinearly indexed random processes) and their decoupled (linearly indexed) comparative counterparts. We here revisit the comparison from [104] and introduce its a \emph{large deviation} upgrade. The new machinery allows to substantially widen the [104]'s range of applicability. In addition to \emph{typical}, studying analytically much harder \emph{atypical} random structures features is now possible as well. To give a bit of a practical flavor, we show how the obtained results connect to the so-called \emph{local entropies} (LE) and their predicated role in understanding solutions clustering and associated \emph{computational gaps} in hard random optimization problems. As was the case in [104], even though the technical considerations often appear as fairly involved, the final interpolating forms admit elegant expressions thereby providing a relatively easy to use tool readily available for further studies. Moreover, as the considered models encompass all well known random structures discussed in [104], the obtained results automatically apply to them as well.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

117 extracted references · 17 canonical work pages

  1. [105]

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

    work page 2025

  2. [104]

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

    arXiv 2023

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

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

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

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

  7. [5]

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

    1990

  8. [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–334. IEEE, 2022

    2022

Show all 117 references
  1. [7]

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

    2022

  2. [8]

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

    2022 arXiv

  3. [9]

    Alweiss, Y

    R. Alweiss, Y. P. Liu, and M. Sawhney. Discrepancy minimization via a self-balancing walk. In Proc. 53rd STOC, ACM, pages 14–20, 2021

    2021

  4. [10]

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

  5. [11]

    Aubin, W

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

    2019

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

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

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

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

  10. [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 . 73

    2023 arXiv

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

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

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

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

  15. [21]

    Bansal and J

    N. Bansal and J. H Spencer. On-line balancing of random inputs. Random Structures & Algorithms , 57(4):879–891, 2020

    2020

  16. [22]

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

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

    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

  19. [25]

    Braunstein and R

    A. Braunstein and R. Zecchina. Learning by message passing in networks of discrete synapses. Physical review letters, 96(3):030201, 2006

    2006

  20. [26]

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

    1960

  21. [27]

    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

  22. [28]

    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

  23. [29]

    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

  24. [30]

    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

  25. [31]

    Fernique

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

    1974

  26. [32]

    Fernique

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

    1975

  27. [33]

    Franz, S

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

    2019

  28. [34]

    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

  29. [35]

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

    2017

  30. [36]

    Franz, A

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

    2019

  31. [37]

    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

  32. [38]

    Gamarnik

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

    2021

  33. [39]

    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

  34. [40]

    Gamarnik, A

    D. Gamarnik, A. Jagannath, and A. S. Wein. Hardness of random optimization problems for Boolean circuits, low-degree polynomials, and Langevin dynamics. SIAM J. Comput. , 53(1):1–46, 2024

    2024

  35. [41]

    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

  36. [42]

    Gamarnik, E

    D. Gamarnik, E. C. Kizildag, W. Perkins, and C. Xu. Geometric barriers for stable and online al- gorithms for discrepancy minimization. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India , volume 195 of Proceedings of Machine...

    2023

  37. [43]

    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

  38. [44]

    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

  39. [45]

    Gamarnik and M

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

    2017

  40. [46]

    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

  41. [47]

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

    1988

  42. [48]

    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

  43. [49]

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

    1985

  44. [50]

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

    2003

  45. [51]

    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

  46. [52]

    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

  47. [53]

    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

  48. [54]

    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

  49. [55]

    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

  50. [56]

    Huang and Y

    H. Huang and Y. Kabashima. Origin of the computational hardness for learning with binary synapses. Phys. Rev. E , 90:052813, 2014

    2014

  51. [57]

    Huang, K

    H. Huang, K. Y. M. Wong, and Y. Kabashima. Entropy landscape of solutions in the binary perceptron problem. Journal of Physics A: Mathematical and Theoretical , 46(37):375002, 2013

    2013

  52. [58]

    Hubara, M

    I. Hubara, M. Courbariaux, D. Soudry, and R. El-Yanivand Y. Bengio. Binarized neural networks. In Advances in Neural Information Processing Systems 29, NeurIPS 2016 , 2016

    2016

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

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

  55. [61]

    Karmarkar, R

    N. Karmarkar, R. M. Karp, G. S Lueker, and A. M. Odlyzko. Probabilistic analysis of optimum partitioning. Journal of Applied probability , 23(3):626–645, 1986

    1986

  56. [62]

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

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

    Ledoux and M

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

    1991

  59. [65]

    Li and T

    S. Li and T. Schramm. Some easy optimization problems have the overlap-gap property. 2020. available online at http://arxiv.org/abs/2411.01836

    2020 arXiv

  60. [66]

    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

  61. [67]

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

    1995

  62. [68]

    Lovett and R

    S. Lovett and R. Meka. Constructive discrepancy minimization by walking on the edges. SIAM Journal on Computing, 44(5):1573–1582, 2015

    2015

  63. [69]

    Mezard, T

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

    2005

  64. [70]

    Montanari

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

    2019

  65. [71]

    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

  66. [72]

    Panchenko

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

    2010

  67. [73]

    Panchenko

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

    2010

  68. [74]

    Panchenko

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

    2013

  69. [75]

    Panchenko

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

    2013

  70. [76]

    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

  71. [77]

    Rahman and B

    M. Rahman and B. Virag. Local algorithms for independent sets are half-optimal. Annals of Probability, 45(3), 2017

    2017

  72. [78]

    Rothvoss

    T. Rothvoss. Constructive discrepancy minimization for convex sets. SIAM Journal on Computing , 46(1):224–234, 2017

    2017

  73. [79]

    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

  74. [80]

    Schlafli

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

    1950

  75. [81]

    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

  76. [82]

    Shcherbina and B

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

    2003

  77. [83]

    Sherrington and S

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

    1972

  78. [84]

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

    1962

  79. [85]

    J. Spencer. Six standard deviations suffice. Transactions of the American mathematical society , 289(2):679–706, 1985

    1985

  80. [86]

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

    arXiv

  81. [87]

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

    arXiv

  82. [88]

    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

  83. [89]

    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

  84. [90]

    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

  85. [91]

    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

  86. [92]

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

    2013 arXiv

  87. [93]

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

    2013 arXiv

  88. [94]

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

    2013 arXiv

  89. [95]

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

    2013 arXiv

  90. [96]

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

    2013 arXiv

  91. [97]

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

    2013 arXiv

  92. [98]

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

    2013

  93. [99]

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

    2013 arXiv

  94. [100]

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

    2016 arXiv

  95. [101]

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

    2016 arXiv

  96. [102]

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

    2023 arXiv

  97. [103]

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

    2023 arXiv

  98. [106]

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

    1971

  99. [107]

    Talagrand

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

    2005

  100. [108]

    Talagrand

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

    2006

  101. [109]

    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

  102. [110]

    Venkatesh

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

    1986

  103. [111]

    A. S Wein. Optimal low-degree hardness of maximum independent set. Mathematical Statistics and Learning, 4(3):221–251, 2022

    2022

  104. [112]

    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

  105. [113]

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

    1962

  106. [114]

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

    1961

  107. [115]

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

    1962

  108. [116]

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

    2021

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