REVIEW 6 major objections 7 minor 1 cited by
Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
T0 review · 6 major / 7 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The paper claims that for the zero-threshold asymmetric binary perceptron, the worst-case local entropy of rare dense solution clusters breaks down for constraint densities $\alpha$ in $(0.77,0.78)$, matching the density at which the best…
desk verdict The numerical result is a known replica prediction, but the paper is a serious methodological exercise applying the author's large-deviation duality machinery to local entropy; its main vulnerability is that the load-bearing theorem is imported from an unpublished companion. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the strong fully lifted large-deviation random duality theorem (Theorem 1, quoted from the companion paper [97]), which equates the random primal free energy of the local-entropy partition function with an optimized fully lifted random dual functional. At the second level of lifting ($r=2$), all terms in the dual reduce to explicit Gaussian expectations: a binary part involving a hyperbolic-cosine factor and a spherical part involving an erfc factor, with the overlap $\bar{\delta}$ enforced through a Lagrange multiplier $\nu$. Theorem 2 then expresses the ground-state local entropy as $f_{sq}(\infty)=-\bar{\psi}_{rd}(\hat{p},\hat{q},\hat{c},\hat{\nu},\hat{\gamma}_{sq},-1)$, and local-entropy breakdown appears exactly when the stationarity conditions have no solution with $\nu\neq 0$.
What would settle it
Compute the same worst-case local entropy for $\kappa=0$, $\alpha=0.78$, and an overlap $\bar{\delta}=0.995$ at the third level of lifting ($r=3$) or by an independent large-deviation or replica method; if a positive entropy or a nonzero $\nu$ solution appears, the claimed breakdown in $(0.77,0.78)$ is an artifact of the $r=2$ truncation. Alternatively, run a state-of-the-art ABP solver at $\alpha=0.78$ and exhibit solutions lying in a dense cluster; that would contradict the predicted structural obstruction.
Extended reading notes
Core claim
For the zero-threshold ABP with capacity $\alpha_c\approx 0.833$, the worst-case local entropy $S_l(\bar{\delta})$ is positive at $\alpha=0.77$ for all overlaps, but at $\alpha=0.78$ it breaks down: for overlaps $\bar{\delta}\in(\bar{\delta}_{c,1},\bar{\delta}_{c,2})$ with $\bar{\delta}_{c,1}\approx 0.993$, the stationarity equations admit no nonzero overlap-enforcing multiplier $\nu$, so there is no exponentially large cluster of solutions at distance $d=(1-\bar{\delta})/2$ from any reference point. This breakdown interval $(0.77,0.78)$ matches the replica predictions of earlier work and the observed algorithmic frontier $\alpha\sim 0.75-0.77$, indicating that the disappearance of rare dense clusters may be a structural signature of the computational gap rather than an incidental feature.
Load-bearing premise
The entire numerical conclusion rests on Theorem 1, the strong fully lifted large-deviation random duality bound quoted from the companion paper [97], which is used without proof; if that theorem fails or does not cover this local-entropy setting, the claimed breakdown interval is unsupported.
Editorial extensions
If this is right
- If the central claim is correct, at $\alpha=0.78$ there is an interval of overlaps $\bar{\delta}\in(0.993,\approx 1)$ for which the worst-case local entropy is negative or vanishing, so no exponentially large cluster surrounds any reference solution at the corresponding Hamming distance.
- The breakdown interval $(0.77,0.78)$ reproduces the replica prediction and sits at the edge of the observed algorithmic frontier $\alpha\approx 0.75-0.77$, making local entropy a candidate structural cause of the ABP computational gap.
- The framework is generic: the same lifted-duality evaluation supplies local entropy for other random feasibility problems such as symmetric binary perceptrons, positive and negative spherical perceptrons, compressed sensing $\ell_1$ thresholds, and discrepancy minimization.
- Across the window from $\alpha=0.77$ to $\alpha=0.78$, the solution-space geometry changes sharply: rare dense clusters persist below the window and defragment above it, giving a concrete phase transition in clustering structure.
- The positive local entropy at $\alpha=0.77$ means efficient algorithms that search for dense connected regions still have exponentially many nearby solutions to find, whereas at $\alpha=0.78$ that resource disappears.
Reading between the lines
- If local-entropy breakdown is the true algorithmic barrier, the same machinery should predict a critical density for every threshold $\kappa$, not just $\kappa=0$; mapping the LE-breakdown curve across the ABP phase diagram would be a direct test of this extension.
- The breakdown interval likely corresponds to an overlap gap in the Hamming-distance distribution of solution pairs, so rigorously connecting local entropy with the overlap gap property could unify two currently separate hardness narratives for the ABP.
- At higher lifting levels the numerical breakpoint may shift slightly within the $(0.77,0.78)$ window; if it converges to a single value, one could conjecture that this value equals the algorithmic threshold $\alpha_{\mathrm{alg}}$, a claim the paper does not yet make.
- Finite-size simulations of solvers that exploit dense clusters should show failure exactly where the predicted entropy breakdown occurs; determining whether algorithmic failure precedes or follows the entropy breakdown in such simulations would clarify whether LE is a cause or a symptom of the computational gap.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the local entropy (LE) of solution clusters of the asymmetric binary perceptron (ABP) as a candidate explanation for the presumed computational gap between the capacity α_c ≈ 0.833 and the empirically solvable range α ≈ 0.75–0.77. The worst-case LE is defined in Eq. (4) as the p→∞-selected maximum, over reference configurations x̄, of the log-partition of solutions at overlap δ̄. Through Laplace-type approximations (Eqs. (5)–(11)) the LE is recast as a ground-state free energy, then evaluated using the author's stationarized fully lifted large-deviation random duality theory (sfl LD RDT): Theorem 1, imported from the companion paper [97], gives a strong duality between a random primal and a fluctuation dual, and Theorem 2 specializes it to the ABP LE in the closed form (35). Solving the r=2 stationarity equations (45)–(55) numerically at α=0.77 and α=0.78 (Figures 1–2, Table 1), the paper reports no LE breakdown at α=0.77 and a breakdown at α=0.78 for overlaps δ̄ ≥ δ̄_{c,1} ≈ 0.993; from this the abstract concludes that LE breaks down in the interval (0.77,0.78), matching the replica predictions of [14] and the algorithmic limit α ≈ 0.75–0.77.
Significance. If the derivation can be made self-contained and rigorous, this would be a valuable methodological contribution: it computes local-entropy-type atypical features via large-deviation random duality rather than replica methods, writes out the r=2 stationarity equations in enough detail to be reproducible (Eqs. (45)–(55)), makes a falsifiable quantitative prediction (breakdown interval and δ̄_{c,1} ≈ 0.993 at α=0.78), and states a generic framework with plausible extensions. The agreement with the replica results [14] and the empirical solver limit is a sensible sanity check. As it stands, the significance is limited: correctness rests on Theorem 1 of the unpublished companion [97] whose hypotheses are not stated; the paper concedes that in a parameter limit its curves are analytically identical to the replica curves of [14], so the quantitative prediction is not new and the identity regime is unspecified; and the numerics cover only two α values without error control. The contribution is better framed as transferring the sfl LD RDT machinery to LE computations, with the ABP breakdown as the worked example, than as a new prediction.
major comments (6)
- [§4, Theorem 1 (Eqs. (15)–(17)) and §4.1 (Eqs. (18)–(31))] The central result, Theorem 1, is imported from the companion manuscript [97], with the proof given in the text as "Follows immediately from Corollary 1 in [97]", and the hypotheses are stated only as "Assume the complete sfl LD RDT frame from [97]". Since Theorem 2 and all numerical conclusions derive exclusively from this theorem, the frame and its domain of validity must be reproduced (at least in an appendix), and the specific choices made here — the function f̄_x(x)=β_z(1^T h(z−κ)−m)−y^T z+νx̄^T x−νδ̄ with unconstrained z, the limits β,β_z,p→∞, s=−1, c_k→c_k/p, and the additional optimization over ν and γ_sq introduced in Eqs. (10)–(11) and (26)–(31) — must be shown to fall within that domain. As written, the hypotheses are not checkable, and the passage from the abstract dual functional (13)–(14) to the concrete dual (18)–(31) changes the problem structure (z is maximized inside D^{(sph)}, Eq. (20)) without an explicit verification. The stationarity conditions (16) are also only necessary conditions; no argument is given that the computed saddle point is global.
- [§3.1, Eqs. (4)–(11), especially Eq. (9)] The local entropy in Eq. (4) involves a simultaneous limit n,β,β_z,p→∞, and Eq. (9) asserts that the ground-state free energy f_sq(∞) equals S_l(δ̄). The order of these limits is never specified, and the interchange of the quenched average, the p→∞ selection, and the β,β_z→∞ limits is not justified; different orders are not a priori equivalent for this reweighted partition function. Similarly, the replacement of max_y and max_z by sums raised to the power −1 in Eq. (5) is a Laplace-type identity that requires z to range over a set of subexponential size or a separate large-deviation argument; for continuous z∈R^m (and the undefined "sum over z" in Eq. (7)) this replacement is not immediate. Because the ground-state limit is the step that turns the free energy into the entropy on which the breakdown claim rests, these interchanges need a rigorous justification or at least a precise statement of the intended order of limits.
- [§4.2, Eq. (43) vs. Eqs. (31) and (55)] The linear term in ν appears as +νδ̄ in Eq. (31) and as δ̄ in the ν-stationarity condition (55), but in the r=2 evaluation, Eq. (43), this term is written as +ν with no factor δ̄. Table 1 reports computations at δ̄=0.99 with ν̂=0.2258 (α=0.77) and ν̂=0.0983 (α=0.78), so the discrepancy is of order 0.001–0.002, which is the same order as the reported entropies S_l=0.0049 and S_l=0.0015. Either the displayed formula is missing the factor δ̄ and the numerical values must be recomputed, or the values were obtained at δ̄=1 and Table 1 is mislabeled. The manuscript must be corrected and the figures re-checked, since the reported S_l values are too small for this discrepancy to be negligible.
- [§4.2, Figures 1–2 and Table 1] The headline interval (0.77,0.78) is inferred from exactly two values of α: absence of breakdown at α=0.77 and presence of breakdown at α=0.78. No error bars, sensitivity analysis with respect to the numerical integrations over U_2 and U_3, or tolerances in the stationarity solver are reported, and the critical overlap δ̄_{c,1} ≈ 0.993 is read off a figure. Moreover, the curve S_max shown in Figure 1 as an upper bound is not defined anywhere in the text. Given that the central claim is a sharp interval statement, the paper should present a scan over α (or at least more bracketing values with error control) and a working definition of S_max.
- [§4.2 and §5 (Conclusion)] The sufficiency of the second level of lifting, r=2, is an assumption: Section 4.2 states that higher levels are "likely to experience tiny refinements" and that "we do not expect major qualitative changes", without proof or numerical check at r=1 or r=3. Since the breakdown interval (0.77,0.78) is the paper's main quantitative output, and the paper itself notes that the key LE features only "appear" at r=2, the stability of the breakdown interval and of δ̄_{c,1} with respect to the lifting level r is a load-bearing, currently unsupported assertion.
- [§4.2 (analytical-identity claim)] Near the end of Section 4.2 the paper states that when δq and δq̂ of [14]'s (B37)–(B49) are close to zero, the present curves "are not only visually similar but also analytically completely identical" to the replica results of [14]. This claim of exact coincidence with existing results is not accompanied by a derivation or by a specification of the parameter regime in which it holds; in particular, the stationary parameters of Table 1 (e.g., q̂_1^{(s)}−q̂_2^{(s)} ≈ 0.58 at α=0.77) do not obviously correspond to a δq→0 regime under the natural scaling. The authors should state precisely which parameters of the r=2 solution vanish in the identity regime, verify whether the solutions used for Figures 1–2 lie in that regime, and clarify what the new derivation adds to the known [14] prediction of the same breakdown interval.
minor comments (7)
- [§4.2, Eq. (52)] The derivative displayed in Eq. (52) is taken with respect to q_2^{(s)} (see Eq. (51)) but is labeled dψ̄_rd/dq_1^{(s)}; the second q-stationarity condition should be labeled dψ̄_rd/dq_2^{(s)} = 0.
- [§4.2, Eq. (49)] In Eq. (49), the sign-function argument is written with h_1^{(2)} appearing twice, whereas Eq. (48) and Eq. (51) use √(q_1−q_2)h_1^{(2)} + √q_2 h_1^{(3)}; the sign argument in Eq. (49) should match Eq. (48).
- [Theorem 2, Eq. (33), and Eq. (36)] Equation (33) contains "nu" in place of the symbol ν in dψ̄_rd(p,q,c,nu,γ_sq,−1)/dc, and Eq. (36) uses the ambiguous notation "1/2β2" where the intended factor appears to be (1/2)β²; the notation should be cleaned up throughout.
- [References [96], [97]; title] References [96] and [97] are cited without arXiv identifiers ("available online at arxiv"); since Theorem 1 depends on [97], the reference should be locatable, and the arXiv header of the manuscript contains a typo ("percept rons").
- [§4, Eqs. (13)–(15)] The notation "‖x‖_2 = x" reuses x for a scalar norm value, and the stated domain R^{3n+m} of f̄_x does not match the natural domain R^{n+2m} of its arguments (x,z,y); these should be cleaned up.
- [§4.1, Eqs. (20), (24)–(25)] The evaluation of D^{(sph)}(s) in Eq. (24) is stated without derivation; since the defining expression (20) contains the term β_z(1−h(z_i−κ)), the authors should show how the β_z→∞ limit (or an equivalent argument) produces the projection expression in Eq. (24).
- [§4.2, concluding paragraphs] The sentence reporting that all calculations were repeated "relying on modulo-m concepts from [96] and [97]" is unexplained; "modulo-m" should be defined or the sentence should be removed, and the analytical-identity claim should state precisely which parameters are sent to zero (see Major Comment 6).
Circularity Check
Central LE formula is imported from the author's Theorem 1 in [97], Theorem 2 is only an immediate corollary, and the paper states that in a limiting case its curves are analytically identical to replica results from [14].
-
self citation load bearing
[Section 4, Theorem 1 (Eqs. (15)-(17)); used again in Theorem 2 (Eq. (35))]
"Theorem 1. [97] Consider large n linear regime where α = lim n→∞ m/n remains constant as n grows and let G ∈ R^{m×n} have independent standard normal elements. ... Assume the complete sfl LD RDT frame from [97] ... Then, lim_{n→∞} E_G ψ_{rp}/n = lim_{n→∞} ψ_{rd}(p̂,q̂,ĉ,s) (strong sfl random duality). Proof. Follows immediately from Corollary 1 in [97]."
The theorem is the sole bridge from the LE partition function to the numerically evaluated Eq. (35); its proof is deferred to [97], the author's own companion preprint, and the required complete sfl LD RDT frame is not reproduced in this paper. Theorem 2's proof is only 'Follows immediately from the previous discussion and Theorem 1', so the headline LE-breakdown interval inherits its content from that self-citation. The paper does not verify the frame's hypotheses, such as compactness/regularity conditions and the β, β_z, p → ∞ with c_k → c_k/p limit.
-
renaming known result
[Section 4.2.1, after Eq. (43)]
"Moreover, the results shown in Figures 1 and 2 seem incredibly similar to the ones in Figure 1 in [14]. Even more remarkable is that when δq and δˆq in [14]'s (B37)-(B49) are close to zero, the curves are not only visually similar but also analytically completely identical."
This admission reduces the RDT-computed LE curves to the replica curves of [14] in the vanishing-δq limit. The advertised result—LE breakdown in the (0.77,0.78) interval—is exactly the phenomenon previously established by [14], so the claimed first-principles prediction is a re-presentation of a known result in RDT language. In that limit the derivation is analytically identical to the prior result, so the new framework is not producing an independent prediction; it is renaming and repackaging the known local-entropy picture.
full rationale
The derivation chain is: define S_l (Eq. 4), rewrite it as f_sq (Eqs. 8-11), invoke Theorem 1 from [97] to replace the random primal by the lifted dual, specialize to binary/spherical sets and s = -1 to obtain Eq. (35), then numerically solve stationarity equations at α = 0.77 and 0.78. The rewriting of S_l as f_sq is by construction but is not itself circular, since it simply defines the quantity being computed. The numerical evaluation is internally coherent and is not fitted to algorithm data or to the replica curves. The circularity burden is concentrated in Theorem 1: the paper gives no proof and no statement of the '[97] frame', and Theorem 2 is explicitly an immediate corollary, so the central formula and the (0.77,0.78) LE-breakdown claim are imported from the author's own companion paper. The further remark that the curves are 'analytically completely identical' to [14] in a limiting case shows that, in that limit, the RDT derivation reproduces known replica results rather than deriving them independently. The r = 2 truncation is an acknowledged expectation rather than a circular step, but it adds fragility to the numerical claim. Overall, the central prediction rests on a load-bearing self-citation chain, with one admitted identity to a known result, so partial circularity is present.
Assumptions & free parameters
assumptions (4)
- domain assumption Strong fully lifted large-deviation random duality (Theorem 1 from [97]) holds.
- ad hoc to paper The second level of lifting (r=2) captures the qualitative behavior; higher levels only refine.
- domain assumption Interchange of limits in the free energy definitions (n, beta, beta_z, p -> infinity) is valid.
- domain assumption The saddle-point stationarity equations yield the correct optimization.
Cite this review
Pith. "Pith review of Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT." pith.science (2026). https://pith.science/paper/NXK274ZP
@misc{pith2026250619276,
author = {Pith},
title = {Pith review of: Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT},
year = {2026},
howpublished = {\url{https://pith.science/paper/NXK274ZP}},
note = {Machine review of arXiv:2506.19276}
}
abstract
We study classical asymmetric binary perceptron (ABP) and associated \emph{local entropy} (LE) as potential source of its algorithmic hardness. Isolation of \emph{typical} ABP solutions in SAT phase seemingly suggests a universal algorithmic hardness. Paradoxically, efficient algorithms do exist even for constraint densities $\alpha$ fairly close but at a finite distance (\emph{computational gap}) from the capacity. In recent years, existence of rare large dense clusters and magical ability of fast algorithms to find them have been posited as the conceptual resolution of this paradox. Monotonicity or breakdown of the LEs associated with such \emph{atypical} clusters are predicated to play a key role in their thinning-out or even complete defragmentation. Invention of fully lifted random duality theory (fl RDT) [90,93,94] allows studying random structures \emph{typical} features. A large deviation upgrade, sfl LD RDT [96,97], moves things further and enables \emph{atypical} features characterizations as well. Utilizing the machinery of [96,97] we here develop a generic framework to study LE as an ABP's atypical feature. Already on the second level of lifting we discover that the LE results are closely matching those obtained through replica methods. For classical zero threshold ABP, we obtain that LE breaks down for $\alpha$ in $(0.77,0.78)$ interval which basically matches $\alpha\sim 0.75-0.77$ range that currently best ABP solvers can handle and effectively indicates that LE's behavior might indeed be among key reflections of the ABP's computational gaps presumable existence.
Figures
Forward citations
Cited by 1 Pith paper
-
CLuP practically achieves $\sim 1.77$ positive and $\sim 0.33$ negative Hopfield model ground state free energy
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
-
[14]
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
-
[97]
M. Stojnic. A large deviation view of stationarized fully lifted blirp interpolation. 2025. available online at arxiv
work page 2025
-
[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: efficient alg orithms can find 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 F
D. Achlioptas and F. Ricci-Tersenghi. On the solution-s pace geometry of random constraint satisfaction problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Comp uting, Seattle, W A, USA, May 21-23, 2006 , pages 130–139. ACM, 2006
2006
-
[5]
A. E. Alaoui, A. Montanari, and M. Sellke. Optimization o f mean-field spin glasses. The Annals of Probability, 49(6), 2021. 16
2021
-
[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
Show all 114 references
-
[7]
A. E. Alaoui and M. Sellke. Algorithmic pure states for th e negative spherical perceptron. Journal of Statistical Physics, 189(27), 2022
2022
-
[8]
D. J. Altschuler. Critical window of the symmetric perce ptron. 2022. available online at http:// arxiv.org/abs/2205.02319
2022 arXiv
-
[9]
Alweiss, Y
R. Alweiss, Y. P. Liu, and M. Sawhney. Discrepancy minimi zation via a self-balancing walk. In Proc. 53rd STOC, ACM , pages 14–20, 2021
2021
-
[10]
A. E. Alaoui amd D. Gamarnik. Hardness of sampling solut ions from the symmetric binary perceptron
-
[11]
Aubin, W
B. Aubin, W. Perkins, and L. Zdeborova. Storage capacit y in symmetric binary perceptrons. J. Phys. A, 52(29):294003, 2019
2019
-
[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
-
[13]
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
-
[15]
Baldassi, C
C. Baldassi, C. Lauditi, E. M. Malatesta, G. Perugini, a nd R. Zecchina. Unveiling the structure of wide flat minima in neural networks. Phys. Rev. Lett. , 127:278301, Dec 2021
2021
-
[16]
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
-
[17]
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
-
[18]
Baldassi, E
C. Baldassi, E. M. Malatesta, and R. Zecchina. Properti es of the geometry of solutions and capacity of multilayer neural networks with rectified linear unit activ ations. Phys. Rev. Lett. , 123:170602, October 2019
2019
-
[19]
Baldassi, R
C. Baldassi, R. D. Vecchia, C. Lucibello, and R. Zecchin a. Clustering of solutions in the symmetric binary perceptron. Journal of Statistical Mechanics: Theory and Experiment , (7):073303, 2020
2020
-
[20]
Baldi and S
P. Baldi and S. Venkatesh. Number od stable points for sp in-glasses and neural networks of higher orders. Phys. Rev. Letters , 58(9):913–916, Mar. 1987
1987
-
[21]
Bansal and J
N. Bansal and J. H Spencer. On-line balancing of random i nputs. Random Structures & Algorithms , 57(4):879–891, 2020
2020
-
[22]
D. Barbier. How to escape atypical regions in the symmet ric binary perceptron: a journey through connected-solutions states. 2024. available online at http://arxiv.org/abs/2408.04479
2024 arXiv
-
[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
-
[24]
Barra, G
A. Barra, G. Genovese, and F. Guerra. The replica symmet ric approximation of the analogical neural network. J. Stat. Physics , July 2010. 17
2010
-
[25]
Barra, G
A. Barra, G. Genovese, F. Guerra, and D. Tantari. How gla ssy are neural networks. J. Stat. Mechanics: Thery and Experiment , July 2012
2012
-
[26]
Bolthausen, S
E. Bolthausen, S. Nakajima, N. Sun, and C. Xu. Gardner fo rmula for Ising perceptron models at small densities. Proceedings of Thirty Fifth Conference on Learning Theory, PML R, 178:1787–1911, 2022
1911
-
[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
-
[28]
Braunstein and R
A. Braunstein and R. Zecchina. Learning by message pass ing in networks of discrete synapses. Physical review letters , 96(3):030201, 2006
2006
-
[29]
S. H. Cameron. Tech-report 60-600. Proceedings of the bionics symposium, pages 197–212, 1960. Wright air development division, Dayton, Ohio
1960
-
[30]
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
-
[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
2008
-
[32]
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
-
[33]
Franz, S
S. Franz, S. Hwang, and P. Urbani. Jamming in multilayer supervised learning models. Phys. Rev. Lett., 123(16):160602, 2019
2019
-
[34]
Franz and G
S. Franz and G. Parisi. Recipes for metastable states in spin glasses. Journal de Physique I , 5(11):1401– 1415, 1995
1995
-
[35]
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
-
[36]
Franz, G
S. Franz, G. Parisi, M. Sevelev, P. Urbani, and F. Zampon i. Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfacti on problems. SciPost Physics , 2:019, 2017
2017
-
[37]
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
-
[38]
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
-
[39]
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
-
[40]
Gamarnik, A
D. Gamarnik, A. Jagannath, and A. S. Wein. Hardness of ra ndom optimization problems for Boolean circuits, low-degree polynomials, and Langevin dynamics. SIAM J. Comput. , 53(1):1–46, 2024
2024
-
[41]
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
-
[42]
Gamarnik, E
D. Gamarnik, E. C. Kizildag, W. Perkins, and C. Xu. Geome tric 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 Machin...
2023
-
[43]
Gamarnik, C
D. Gamarnik, C. Moore, and L. Zdeborova. Disordered sys tems insights on computational hardness. Journal of Statistical Mechanics: Theory and Experiment , (11):115015, 2022. 18
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]
Gutfreund and Y
H. Gutfreund and Y. Stein. Capacity of neural networks w ith discrete synaptic couplings. J. Physics A: Math. Gen , 23:2613, 1990
1990
-
[50]
D. O. Hebb. Organization of behavior. New York: Wiley , 1949
1949
-
[51]
J. J. Hopfield. Neural networks and physical systems wit h emergent collective computational abilities. Proc. Nat. Acad. Science , 79:2554, 1982
1982
-
[52]
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
-
[53]
Huang and M
B. Huang and M. Sellke. Tight lipschitz hardness for opt imizing mean field spin glasses. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2 022, Denver, CO, USA, October 31 - November 3, 2022 , pages 312–322. IEEE, 2022
2022
-
[54]
Huang and Y
H. Huang and Y. Kabashima. Origin of the computational h ardness for learning with binary synapses. Phys. Rev. E , 90:052813, 2014
2014
-
[55]
Huang, K
H. Huang, K. Y. M. Wong, and Y. Kabashima. Entropy landsc ape of solutions in the binary perceptron problem. Journal of Physics A: Mathematical and Theoretical , 46(37):375002, 2013
2013
-
[56]
Hubara, M
I. Hubara, M. Courbariaux, D. Soudry, and R. El-Yanivan d Y. Bengio. Binarized neural networks. In Advances in Neural Information Processing Systems 29, NeurIPS 2 016, 2016
2016
-
[57]
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
-
[58]
Karmarkar, R
N. Karmarkar, R. M. Karp, G. S Lueker, and A. M. Odlyzko. P robabilistic analysis of optimum partitioning. Journal of Applied probability , 23(3):626–645, 1986
1986
-
[59]
J. H. Kim and J. R. Roche. Covering cubes by random half cu bes with applications to biniary neural networks. Journal of Computer and System Sciences , 56:223–252, 1998
1998
-
[60]
E. C. Kizildag. Sharp phase transition for multi overla p gap property in ising p-spin glass and random k-SAT models. 2023. available online at http://arxiv.org/abs/2309.09913
2023 arXiv
-
[61]
Krauth and M
W. Krauth and M. Mezard. Storage capacity of memory netw orks with binary couplings. J. Phys. France, 50:3057–3066, 1989
1989
-
[62]
Li and T
S. Li and T. Schramm. Some easy optimization problems ha ve the overlap-gap property. 2020. available online at http://arxiv.org/abs/2411.01836
2020 arXiv
-
[63]
S. Li, T. Schramm, and K. Zhou. Discrepancy algorithms f or the binary perceptron. 2024. available online at http://arxiv.org/abs/2408.00796. 19
2024 arXiv
-
[64]
Lovett and R
S. Lovett and R. Meka. Constructive discrepancy minimi zation by walking on the edges. SIAM Journal on Computing , 44(5):1573–1582, 2015
2015
-
[65]
Mezard, T
M. Mezard, T. Mora, and R. Zecchina. Clustering of solut ions in the random satisfiability problem. Physical Review Letters , 94:197204, 2005
2005
-
[66]
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
-
[67]
Nakajima and N
S. Nakajima and N. Sun. Sharp threshold sequence and uni versality for Ising perceptron models. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discret e Algorithms (SODA) , pages 638– 674, 2023
2023
-
[68]
Pastur and A
L. Pastur and A. Figotin. On the theory of disordered spi n systems. Theory Math. Phys. , 35(403-414), 1978
1978
-
[69]
Pastur, M
L. Pastur, M. Shcherbina, and B. Tirozzi. The replica-s ymmetric solution without the replica trick for the Hopfield model. Journal of Statistical Physics , 74(5/6), 1994
1994
-
[70]
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
-
[71]
Rahman and B
M. Rahman and B. Virag. Local algorithms for independen t sets are half-optimal. Annals of Probability, 45(3), 2017
2017
-
[72]
Rothvoss
T. Rothvoss. Constructive discrepancy minimization f or convex sets. SIAM Journal on Computing , 46(1):224–234, 2017
2017
-
[73]
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 (F OCS), pages 2369–2382, 2023
2023
-
[74]
L. Schlafli. Gesammelte Mathematische AbhandLungen I . Basel, Switzerland: Verlag Birkhauser, 1950
1950
-
[75]
Shcherbina and B
M. Shcherbina and B. Tirozzi. The free energy of a class o f Hopfield models. Journal of Statistical Physics, 72(1/2), 1993
1993
-
[76]
Shcherbina and B
M. Shcherbina and B. Tirozzi. On the volume of the intrer section of a sphere with random half spaces. C. R. Acad. Sci. Paris. Ser I , (334):803–806, 2002
2002
-
[77]
Shcherbina and B
M. Shcherbina and B. Tirozzi. Rigorous solution of the G ardner problem. Comm. on Math. Physics , (234):383–422, 2003
2003
-
[78]
Sherrington and S
D. Sherrington and S. Kirkpatrick. Solvable model of a s pin glass. Phys. Rev. Letters , 35:1792–1796, 1972
1972
-
[79]
J. Spencer. Six standard deviations suffice. Transactions of the American mathematical society , 289(2):679–706, 1985
1985
-
[80]
M. Stojnic. Various thresholds for ℓ1-optimization in compressed sensing. available online at http:// arxiv.org/abs/0907.3666
-
[81]
M. Stojnic. A simple performance analysis of ℓ1-optimization in compressed sensing. ICASSP, Inter- national Conference on Acoustics, Signal and Speech Proces sing, April 2009
2009
-
[82]
M. Stojnic. ℓ1 optimization and its various thresholds in compressed sens ing. ICASSP, IEEE Inter- national Conference on Acoustics, Signal and Speech Proces sing, pages 3910–3913, 14-19 March 2010. Dallas, TX. 20
2010
-
[83]
M. Stojnic. Another look at the Gardner problem. 2013. a vailable online at http://arxiv.org/abs/ 1306.3979
2013 arXiv
-
[84]
M. Stojnic. Discrete perceptrons. 2013. available onl ine at http://arxiv.org/abs/1303.4375
2013 arXiv
-
[85]
M. Stojnic. Lifting ℓ1-optimization strong and sectional thresholds. 2013. avai lable online at http:// arxiv.org/abs/1306.3770
2013 arXiv
-
[86]
M. Stojnic. Lifting/lowering Hopfield models ground st ate energies. 2013. available online at http:// arxiv.org/abs/1306.3975
2013 arXiv
-
[87]
M. Stojnic. Negative spherical perceptron. 2013. avai lable online at http://arxiv.org/abs/1306. 3980
2013
-
[88]
M. Stojnic. Regularly random duality. 2013. available online at http://arxiv.org/abs/1303.7295
2013 arXiv
-
[89]
M. Stojnic. Spherical perceptron as a storage memory wi th limited errors. 2013. available online at http://arxiv.org/abs/1306.3809
2013 arXiv
-
[90]
M. Stojnic. Bilinearly indexed random processes – stationarization of fully lifted interpolation. 2023. available online at http://arxiv.org/abs/2311.18097
2023 arXiv
-
[91]
M. Stojnic. Binary perceptrons capacity via fully lift ed random duality theory. 2023. available online at http://arxiv.org/abs/2312.00073
2023 arXiv
-
[92]
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
-
[93]
M. Stojnic. Fully lifted interpolating comparisons of bilinearly indexed random processes. 2023. available online at http://arxiv.org/abs/2311.18092
2023 arXiv
-
[94]
M. Stojnic. Fully lifted random duality theory. 2023. a vailable online at http://arxiv.org/abs/ 2312.00070
2023 arXiv
-
[95]
M. Stojnic. Studying Hopfield models via fully lifted ra ndom duality theory. 2023. available online at http://arxiv.org/abs/2312.00071
2023 arXiv
-
[96]
M. Stojnic. Fully lifted blirp interpolation – a large deviation view. 2025. available onl ine at arxiv
2025
-
[98]
The complexity of spherical p-spin models - A se cond moment approach
E Subag. The complexity of spherical p-spin models - A se cond moment approach. Ann. Probab., 45:3385 – 3450, 2017
2017
-
[99]
The geometry of the gibbs measure of pure spheri cal spin glasses
E Subag. The geometry of the gibbs measure of pure spheri cal spin glasses. Inventiones Mathematicae, 210:135 – 209, 2017
2017
-
[100]
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
-
[101]
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
-
[102]
Talagrand
M. Talagrand. Rigorous results for the Hopfield models with many patterns. Prob. Theor. Rel. Fields , 110:109–176, 1998
1998
-
[103]
Talagrand
M. Talagrand. The Generic Chaining . Springer-Verlag, 2005
2005
-
[104]
Talagrand
M. Talagrand. Mean field models and spin glasse: Volume II . A series of modern surveys in mathematics 55, Springer-Verlag, Berlin Heidelberg, 2011. 21
2011
-
[105]
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
-
[106]
Venkatesh
S. Venkatesh. Epsilon capacity of neural networks. Proc. Conf. on Neural Networks for Computing, Snowbird, UT , 1986
1986
-
[107]
A. S Wein. Optimal low-degree hardness of maximum inde pendent set. Mathematical Statistics and Learning, 4(3):221–251, 2022
2022
-
[108]
J. G. Wendel. A problem in geometric probability. Mathematica Scandinavica, 1:109–111, 1962
1962
-
[109]
J. G. Wendel. A problem in geometric probablity. Mathematics Scandinavia, 11:109–111, 1962
1962
-
[110]
R. O. Winder. Single stage threshold logic. Switching circuit theory and logical design , pages 321–332, Sep. 1961. AIEE Special publications S-134
1961
-
[111]
R. O. Winder. Threshold logic. Ph. D. dissertation, Princetoin University, 1962
1962
-
[112]
C. Xu. Sharp threshold for the Ising perceptron model. Ann. Probab., 43(5):2399–2415, 2021
2021
-
[113]
J. Y. Zhao. The Hopfield model with superlinearly many p atterns. 2011. available online at http:// arxiv.org/abs/1108.4771. 22
2011 arXiv
-
[2024]
available online at http://arxiv.org/abs/2407.16627
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.