pith. sign in

arxiv: 2604.19712 · v1 · submitted 2026-04-21 · 💻 cs.LG · cond-mat.dis-nn· cs.IT· math.IT· math.PR· stat.ML

Ultrametric OGP - parametric RDT symmetric binary perceptron connection

Mihailo Stojnic This is my paper

Pith reviewed 2026-05-10 03:05 UTC · model grok-4.3

classification 💻 cs.LG cond-mat.dis-nncs.ITmath.ITmath.PRstat.ML
keywords ultrametric overlap gap propertyparametric RDTsymmetric binary perceptronalgorithmic thresholdunion boundstatistical computational gapreplica methodsolution space geometry
0
0 comments X

The pith

Ultrametric overlap gap upper bounds for symmetric binary perceptrons numerically match successive parametric RDT estimates and are conjectured to share their infinite-level limit.

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

The paper computes rigorous upper bounds on the allowable constraint density for s-level ultrametric overlap gap properties in symmetric binary perceptrons. These bounds are obtained by a union-bounding argument that splits into a convex combinatorial optimization and a nested probabilistic integral. At the first two levels the resulting numerical values sit within 0.0002 of the third- and fourth-level parametric RDT thresholds. The observed agreement prompts the conjecture that both sequences converge to the same algorithmic threshold as the level tends to infinity and that the two frameworks are related by an exact isomorphism.

Core claim

For any positive integer s the s-level ultrametric OGP density satisfies α_ult_s ≤ α_c^(s+2), with numerical evidence indicating that equality holds for small s and that the common infinite-level limit equals the algorithmic threshold α_a previously estimated by parametric RDT.

What carries the argument

s-level ultrametric OGP with an analytical union bound whose combinatorial part is cast as a convex program and whose probabilistic part is evaluated by nested integration.

If this is right

  • The algorithmic threshold α_a equals both the infinite-s limit of the ultrametric OGP densities and the infinite-r limit of the parametric RDT thresholds.
  • Overlap values and relative sizes of ultrametric clusters coincide with the corresponding quantities extracted from the parametric RDT.
  • A full isomorphism exists that maps every key parameter of the ultrametric OGP description onto its parametric RDT counterpart.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the conjectured isomorphism holds, the same limiting threshold should appear in other models whose solution spaces admit ultrametric structure, such as certain spin-glass or constraint-satisfaction problems.
  • Higher-level computations could be used to decide whether the inequality α_ult_s ≤ α_c^(s+2) is strict or becomes equality for all sufficiently large s.
  • The union-bound technique developed here may be portable to other geometric properties of solution spaces once they are expressed in ultrametric form.

Load-bearing premise

The close numerical match between the newly computed ultrametric bounds and earlier RDT values reflects an exact isomorphism rather than coincidental agreement at low levels.

What would settle it

Direct computation of the ultrametric bound at s=5 (or higher) that deviates from α_c^(7) by more than numerical precision or that stops approaching the local-entropy value 1.58.

Figures

Figures reproduced from arXiv: 2604.19712 by Mihailo Stojnic.

Figure 1
Figure 1. Figure 1: Upper bounds α¯ult1 (1; k) on αkogp(1) and αult1 (1) = limk→∞ αkogp(1). ≤ X X∈X (k;Q) P [PITH_FULL_IMAGE:figures/full_fig_p022_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Upper bounds α¯ult2 (1; k) on ultrametric OGP critical constraint density αult2 (1). happens on higher levels of ultrametricity might shed some light on whether there is indeed such a connection. Proceeding in that direction at present is not a smooth process as overcoming memory requirements appears rather challenging. Nonetheless, we conducted some limited evaluations on the third ultrametric level and w… view at source ↗
Figure 3
Figure 3. Figure 3: Upper bounds α¯ults (1; k) on ultrametric OGP critical constraint density αults (1). where ks ks−1 , ks−1 ks−2 , . . . , k2 k1 , k1 k0 ∈ Z. (171) Set cw1 = 1 1 − q1 cw(i+1) = −   X i j=1 kj−1cwj   2   1 qi − qi+1 + ki X i j=1 kj−1cwj   −1 , i = 1, 2, . . . , s, z = [z1, z2, . . . , zs] D(s) = Xs i=1 p−cw(i+1) √ cw1 zi E (s) = √ cw1κ, (172) and ˜I (s) 0 (z) = − e (D(s) ) 2 2  erf  √ 2 D(s) 2 − √ 2… view at source ↗
read the original abstract

In [97,99,100], an fl-RDT framework is introduced to characterize \emph{statistical computational gaps} (SCGs). Studying \emph{symmetric binary perceptrons} (SBPs), [100] obtained an \emph{algorithmic} threshold estimate $\alpha_a\approx \alpha_c^{(7)}\approx 1.6093$ at the 7th lifting level (for $\kappa=1$ margin), closely approaching $1.58$ local entropy (LE) prediction [18]. In this paper, we further connect parametric RDT to overlap gap properties (OGPs), another key geometric feature of the solution space. Specifically, for any positive integer $s$, we consider $s$-level ultrametric OGPs ($ult_s$-OGPs) and rigorously upper-bound the associated constraint densities $\alpha_{ult_s}$. To achieve this, we develop an analytical union-bounding program consisting of combinatorial and probabilistic components. By casting the combinatorial part as a convex problem and the probabilistic part as a nested integration, we conduct numerical evaluations and obtain that the tightest bounds at the first two levels, $\bar{\alpha}_{ult_1} \approx 1.6578$ and $\bar{\alpha}_{ult_2} \approx 1.6219$, closely approach the 3rd and 4th lifting level parametric RDT estimates, $\alpha_c^{(3)} \approx 1.6576$ and $\alpha_c^{(4)} \approx 1.6218$. We also observe excellent agreement across other key parameters, including overlap values and the relative sizes of ultrametric clusters. Based on these observations, we propose several conjectures linking $ult$-OGP and parametric RDT. Specifically, we conjecture that algorithmic threshold $\alpha_a=\lim_{s\rightarrow\infty} \alpha_{ult_s} = \lim_{s\rightarrow\infty} \bar{\alpha}{ult_s} = \lim_{r\rightarrow\infty} \alpha_{c}^{(r)}$, and $\alpha_{ult_s} \leq \alpha_{c}^{(s+2)}$ (with possible equality for some (maybe even all) $s$). Finally, we discuss the potential existence of a full isomorphism connecting all key parameters of $ult$-OGP and parametric RDT.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript derives rigorous upper bounds on the constraint densities α_ult_s for s-level ultrametric overlap gap properties (ult_s-OGPs) in symmetric binary perceptrons. These bounds are obtained from an analytical union bound whose combinatorial component is cast as a convex program and whose probabilistic component is evaluated via nested integrals. Numerical evaluation yields tightest bounds of approximately 1.6578 at s=1 and 1.6219 at s=2, which closely match the author's prior parametric RDT estimates α_c^(3)≈1.6576 and α_c^(4)≈1.6218; similar agreement is reported for overlap values and ultrametric cluster sizes. The paper conjectures that the algorithmic threshold α_a equals the infinite-level limits of both sequences and that α_ult_s ≤ α_c^(s+2), with a possible full isomorphism between the frameworks.

Significance. The rigorous union-bound derivation of the ult_s-OGP upper bounds is a solid technical contribution to the geometric analysis of solution spaces in high-dimensional inference. If the conjectured isomorphism holds, the work would provide a direct geometric interpretation of the parametric RDT thresholds via ultrametric OGPs, strengthening the understanding of statistical-computational gaps for the symmetric binary perceptron. The multi-parameter numerical agreement supplies suggestive evidence for the conjectures, though analytic confirmation would be required to elevate the connection beyond observation.

major comments (2)
  1. [Numerical Results] Numerical Results section: the reported matches (e.g., bar{α}_ult_1 ≈ 1.6578 vs α_c^(3) ≈ 1.6576 and bar{α}_ult_2 ≈ 1.6219 vs α_c^(4) ≈ 1.6218) are presented to four decimal places without error bounds, solver tolerances, convergence diagnostics, or cross-validation against alternative quadrature or optimization methods. Because the conjectures of exact equality in the limit and the proposed isomorphism rest on this closeness, quantitative precision analysis is needed to rule out approximation artifacts on the scale of 10^{-4}.
  2. [Conjectures] Conjectures (abstract and final discussion): the claims α_a = lim_{s→∞} α_ult_s = lim_{r→∞} α_c^(r) and α_ult_s ≤ α_c^(s+2) are supported by numerical agreement with values taken from the author's prior works [97,99,100]. While the OGP bounds themselves are newly derived, an independent verification or analytic argument establishing the structural isomorphism (rather than low-level numerical coincidence) is required to make the central connection load-bearing.
minor comments (1)
  1. [Abstract] Abstract: the phrase 'excellent agreement across other key parameters' should explicitly name the parameters (overlap values, cluster sizes) to improve readability before the reader reaches the numerical section.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the thorough review and valuable comments on our manuscript. We address each major point below and have revised the manuscript to incorporate additional numerical diagnostics where feasible. The conjectures remain supported by the observed multi-parameter agreements but are presented as such.

read point-by-point responses

  1. Referee: [Numerical Results] Numerical Results section: the reported matches (e.g., bar{α}_ult_1 ≈ 1.6578 vs α_c^(3) ≈ 1.6576 and bar{α}_ult_2 ≈ 1.6219 vs α_c^(4) ≈ 1.6218) are presented to four decimal places without error bounds, solver tolerances, convergence diagnostics, or cross-validation against alternative quadrature or optimization methods. Because the conjectures of exact equality in the limit and the proposed isomorphism rest on this closeness, quantitative precision analysis is needed to rule out approximation artifacts on the scale of 10^{-4}.

    Authors: We agree that additional precision analysis strengthens the presentation. In the revised manuscript, we have added a new subsection detailing the convex solver tolerances (set to 1e-8 relative gap), the nested quadrature scheme (adaptive Gauss-Kronrod with 10^{-6} absolute tolerance), and results from 50 independent runs with varied initializations and grid refinements. These yield standard deviations below 5e-5 for the reported α_ult_s values, confirming that the 10^{-4}-scale matches with the parametric RDT thresholds are not artifacts of numerical approximation. revision: yes

  2. Referee: [Conjectures] Conjectures (abstract and final discussion): the claims α_a = lim_{s→∞} α_ult_s = lim_{r→∞} α_c^(r) and α_ult_s ≤ α_c^(s+2) are supported by numerical agreement with values taken from the author's prior works [97,99,100]. While the OGP bounds themselves are newly derived, an independent verification or analytic argument establishing the structural isomorphism (rather than low-level numerical coincidence) is required to make the central connection load-bearing.

    Authors: The conjectures are formulated precisely as numerical observations across thresholds, overlaps, and cluster sizes, not as proven equalities. The manuscript already qualifies them as conjectures in the abstract and discussion. While we cannot supply an analytic isomorphism proof within the current scope (which centers on the union-bound derivation of the OGP thresholds), the consistency across independent parameter sets provides non-trivial evidence beyond coincidence. We have expanded the discussion to emphasize the conjectural nature and to outline potential directions for future analytic work connecting the two frameworks. revision: partial

standing simulated objections not resolved
  • Providing a full analytic proof of the structural isomorphism between ultrametric OGP and parametric RDT frameworks.

Circularity Check

0 steps flagged

No significant circularity; new OGP upper bounds derived independently and conjecturally compared to prior RDT estimates

full rationale

The paper derives fresh upper bounds on α_ult_s via an analytical union-bounding program (combinatorial part as convex optimization, probabilistic part as nested integrals) that is self-contained and does not reference or depend on the parametric RDT quantities. Numerical values such as bar α_ult_1 ≈ 1.6578 are obtained directly from this program and then observed to be close to α_c^{(3)} ≈ 1.6576 from prior work. The conjectures (α_a = lim α_ult_s = lim α_c^{(r)} and α_ult_s ≤ α_c^{(s+2)}) are explicitly labeled as conjectures motivated by the numerical agreement and overlap/cluster-size matches; they are not presented as derived equalities or first-principles results. No equation, bound, or limit in the new derivation reduces by construction to the cited RDT expressions. Self-citation is present for context and comparison values but is not load-bearing for any claimed derivation or prediction.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The analysis extends the author's prior fl-RDT framework by adding an ultrametric OGP layer; it relies on standard probabilistic union bounds and convexity but introduces no new physical postulates. The numerical matches depend on the same margin parameter κ=1 used in the referenced prior work.

free parameters (2)
  • lifting level r
    Integer parameter controlling the depth of the parametric RDT approximation; values 3 and 4 are compared to OGP levels 1 and 2.
  • ultrametric level s
    Positive integer controlling the depth of the ultrametric OGP hierarchy; bounds computed explicitly for s=1 and s=2.
axioms (2)
  • standard math The union bound supplies a valid (possibly loose) upper bound on the probability that an ultrametric OGP occurs.
    Invoked to convert the combinatorial-probabilistic counting program into an upper bound on α_ult_s.
  • domain assumption The combinatorial counting problem can be relaxed to a convex optimization problem without changing the location of the threshold.
    Used to make the union-bound program numerically tractable.

pith-pipeline@v0.9.0 · 5756 in / 1875 out tokens · 64479 ms · 2026-05-10T03:05:34.419184+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

114 extracted references · 114 canonical work pages

  1. [1]

    E. Abbe, S. Li, and A. Sly. Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 327–338. IEEE, 2021

    work page 2021

  2. [2]

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

    work page 2022

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

    work page 2011

  4. [4]

    Achlioptas and F

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

    work page 2006

  5. [5]

    El Alaoui and D

    A. El Alaoui and D. Gamarnik. Hardness of sampling solutions from the symmetric binary perceptron. Random Struct. Algorithms, 66(4), 2025

    work page 2025

  6. [6]

    El Alaoui, A

    A. El Alaoui, A. Montanari, and M. Sellke. Optimization of mean-field spin glasses.The Annals of Probability, 49(6), 2021

    work page 2021

  7. [7]

    El Alaoui, A

    A. El Alaoui, A. Montanari, and M. Sellke. Sampling from the Sherrington-Kirkpatrick gibbs measure via algorithmic stochastic localization. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 323–334. IEEE, 2022

    work page 2022

  8. [8]

    El Alaoui and M

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

    work page 2022

  9. [9]

    D. J. Altschuler. Critical window of the symmetric perceptron.Electron. J. Probab, 28:1–28, 2023

    work page 2023

  10. [10]

    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

    work page 2021

  11. [11]

    E. Amaldi. On the complexity of training perceptrons. InT. Kohonen, K. Makisara, O. Simula, and J. Kangas, editors, Artificial neural networks. Elsevier Amsterdam, pages 55–60, 1991

    work page 1991

  12. [12]

    B. L. Annesi, E. M. Malatesta, and F. Zamponi. Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks.SciPost Phys., 18:118, 2025

    work page 2025

  13. [13]

    Aubin, W

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

    work page 2019

  14. [14]

    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

    work page 2007

  15. [15]

    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

    work page 2015

  16. [16]

    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

    work page 2016

  17. [17]

    Typicalandatypicalsolutionsinnonconvex neural networks with discrete and continuous weights.Phys

    C.Baldassi, E.M.Malatesta, G.Perugini, andR.Zecchina. Typicalandatypicalsolutionsinnonconvex neural networks with discrete and continuous weights.Phys. Rev. E, 108:024310, Aug 2023

    work page 2023

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

    work page 2020

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

    work page 1987

  20. [20]

    Bansal and J

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

    work page 2020

  21. [21]

    D. Barbier. How to escape atypical regions in the symmetric binary perceptron: A journey through connected-solutions states.SciPost Phys., 18:115, 2025

    work page 2025

  22. [22]

    Barbier, A

    D. Barbier, A. El 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

    work page 2024

  23. [23]

    Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models

    J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová. Optimal errors and phase transi- tions in high-dimensional generalized linear models. InConference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 ofProceedings of Machine Learning Research, pages 728–731. PMLR, 2018. available online athttp://arxiv.org/abs/1708.03395. 44

    work page Pith review arXiv 2018

  24. [24]

    Bhamidi, D

    S. Bhamidi, D. Gamarnik, and S. Gong. Finding a dense submatrix of a random matrix. sharp bounds for online algorithms.Electron. Commun. Probab., 31, 2026

    work page 2026

  25. [25]

    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

    work page 1911

  26. [26]

    Braunstein and R

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

    work page 2006

  27. [27]

    Bresler and B

    G. Bresler and B. Huang. The algorithmic phase transition of random k-SAT for low degree poly- nomials. In62th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 298–309. IEEE, 2021

    work page 2021

  28. [28]

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

    work page 1960

  29. [29]

    W.-K. Chen, D. Gamarnik, D. Panchenko, and M. Rahman. Suboptimality of local algorithms for a class of max-cut problems.The Annals of Probability, 47(3):1587–1618, 2019

    work page 2019

  30. [30]

    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

    work page 1965

  31. [31]

    Daude, M

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

    work page 2008

  32. [32]

    Dhawan, E

    A. Dhawan, E. C. Kizildag, and N. Maitra. Sharp online hardness for large balanced independent sets

    work page

  33. [33]

    available online athttp://arxiv.org/abs/2508.20785

    work page arXiv

  34. [34]

    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

    work page 2019

  35. [35]

    H. Du, S. Gong, and R. Huang. The algorithmic phase transition of random graph alignment problem. Probab. Theory Related Fields, 191:1233–1288, 2025

    work page 2025

  36. [36]

    Franz, S

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

    work page 2019

  37. [37]

    Franz and G

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

    work page 2016

  38. [38]

    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

    work page 2017

  39. [39]

    Franz, A

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

    work page 2019

  40. [40]

    Franz, A

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

    work page 2020

  41. [41]

    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

    work page 2021

  42. [42]

    Theoverlapgappropertyandapproximatemessagepassingalgorithms for p-spin models.Ann

    D.GamarnikandA.Jagannath. Theoverlapgappropertyandapproximatemessagepassingalgorithms for p-spin models.Ann. Probab., 49:180 – 205, 2021

    work page 2021

  43. [43]

    Gamarnik, A

    D. Gamarnik, A. Jagannath, and E. C. Kizildag. Shattering in the Ising pure p-spin model.Probab. Theory Relat. Fields, 193:89–141, 2025

    work page 2025

  44. [44]

    Gamarnik, A

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

    work page 2020

  45. [45]

    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

    work page 2024

  46. [46]

    Gamarnik, E

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

    work page 2022

  47. [47]

    Gamarnik, E

    D. Gamarnik, E. C. Kizildag, W. Perkins, and C. Xu. Geometric barriers for stable and online al- gorithms for discrepancy minimization. InThe Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 ofProceedings of Machine Learning Re- search, pages 3231–3263. PMLR, 2023

    work page 2023

  48. [48]

    Optimal Hardness of Online Algo- rithms for Large Independent Sets

    D. Gamarnik, E. C. Kizildag, and L. Warnke. Optimal hardness of online algorithms for large inde- pendent sets. 2025. available online athttp://arxiv.org/abs/2504.11450

    work page arXiv 2025

  49. [49]

    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

    work page 2022

  50. [50]

    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

    work page 2014

  51. [51]

    Gamarnik and M

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

    work page 2017

  52. [52]

    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

    work page 2017

  53. [53]

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

    work page 1988

  54. [54]

    Gardner and B

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

    work page 1988

  55. [55]

    S. Gong, B. Huang, S. Li, and M. Sellke. Stable algorithms cannot reliably find isolated perceptron solutions. 2026. available online athttp://arxiv.org/abs/2604.00328

    work page arXiv 2026

  56. [56]

    Gutfreund and Y

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

    work page 1990

  57. [57]

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

    work page 2024

  58. [58]

    Huang and M

    B. Huang and M. Sellke. Tight Lipschitz hardness for optimizing mean field spin glasses. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 312–322. IEEE, 2022

    work page 2022

  59. [59]

    Algorithmic threshold for multi-species spherical spin glasses

    B. Huang and M. Sellke. Algorithmic threshold for multi-species spherical spin glasses. 2023. available online athttp://arxiv.org/abs/2303.12172

    work page arXiv 2023

  60. [60]

    Huang and M

    B. Huang and M. Sellke. Optimization algorithms for multi-species spherical spin glasses.J. Stat. Phys., 191, 2024

    work page 2024

  61. [61]

    Strong Low Degree Hardness for Stable Local Optima in Spin Glasses

    B. Huang and M. Sellke. Strong low degree hardness for stable local optima in spin glasses. 2025. available online athttp://arxiv.org/abs/2501.06427

    work page arXiv 2025

  62. [62]

    Huang and M

    B. Huang and M. Sellke. Tight Lipschitz hardness for optimizing mean field spin glasses.Comm. Pure. Appl. Math., 78(1):60–119, 2025

    work page 2025

  63. [63]

    Huang and Y

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

    work page 2014

  64. [64]

    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

    work page 2013

  65. [65]

    Hubara, M

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

    work page 2016

  66. [66]

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

    work page 1960

  67. [67]

    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

    work page 1986

  68. [68]

    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

    work page 1998

  69. [69]

    E. C. Kizildag. Sharp phase transition for multi overlap gap property in Ising p-spin glass and random k-SAT models. 2023. available online athttp://arxiv.org/abs/2309.09913

    work page arXiv 2023

  70. [70]

    Krauth and M

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

    work page 1989

  71. [71]

    Krzakala, M

    F. Krzakala, M. Mézard, F. Sausset, Y. F. Sun, and L. Zdeborová. Probabilistic reconstruction in com- pressed sensing: algorithms, phase diagrams, and threshold achieving matrices.Journal of Statistical Mechanics: Theory and Experiment, page P08009, 2012

    work page 2012

  72. [72]

    Li and T

    S. Li and T. Schramm. Some easy optimization problems have the overlap-gap property. InThe Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France, volume 291 of Proceedings of Machine Learning Research, pages 3582–3622. PMLR, 2025

    work page 2025

  73. [73]

    S. Li, T. Schramm, and K. Zhou. Discrepancy algorithms for the binary perceptron. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1668–1679. ACM, 2025

    work page 2025

  74. [74]

    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

    work page 2015

  75. [75]

    Mezard, T

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

    work page 2005

  76. [76]

    Montanari

    A. Montanari. Optimization of the Sherrington-Kirkpatrick hamiltonian. In60th 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

    work page 2019

  77. [77]

    J.-C. Mourrat. Un-inverting the Parisi formula.Ann. Inst. H. Poincare Probab. Statist., 61(4):2709– 2720, November 2025

    work page 2025

  78. [78]

    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

    work page 2023

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

    work page 2021

  80. [80]

    Rahman and B

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

    work page 2017

Showing first 80 references.