mlsanityData to 14 Oct 2026

Ultrametric OGP - parametric RDT symmetric binary perceptron connection

arXiv 2604.19712 ↗First posted 21 Apr 2026cs.LG cond-mat.dis-nn cs.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

In [97,99,100], an fl-RDT framework is introduced to characterize statistical computational gaps (SCGs). Studying symmetric binary perceptrons (SBPs), [100] obtained an algorithmic threshold estimate αa≈ αc(7)≈ 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 (ults-OGPs) and rigorously upper-bound the associated constraint densities αults. 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αult1 ≈ 1.6578 and barαult2 ≈ 1.6219, closely approach the 3rd and 4th lifting level parametric RDT estimates, αc(3) ≈ 1.6576 and αc(4) ≈ 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 αa=limsrightarrow∞ αults = limsrightarrow∞ barαults = limrrightarrow∞ αc(r), and αults ≤ α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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 44 of its 109 references that are in the map. First posted on arXiv 21 Apr 2026.

Builds on

44 of 109 references.

References · 44

  1. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
  2. 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
  3. 2015Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapsescited by 39
  4. 2013Another look at the Gardner problemcited by 24
  5. 2013Limits of local algorithms over sparse random graphscited by 23
  6. 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
  7. 2015Local entropy as a measure for sampling solutions in Constraint Satisfaction Problemscited by 20
  8. 2018Optimization of the Sherrington-Kirkpatrick Hamiltoniancited by 20
  9. 2021Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptroncited by 18
  10. 2023Fully lifted random duality theorycited by 18
  11. 2014Origin of the computational hardness for learning with binary synapsescited by 16
  12. 2020Optimal Low-Degree Hardness of Maximum Independent Setcited by 16
32 more
  1. 2013Discrete perceptronscited by 14
  2. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  3. 2020Algorithmic pure states for the negative spherical perceptroncited by 13
  4. 2021Binary perceptron: efficient algorithms can find solutions in a rare well-connected clustercited by 13
  5. 2023Typical and atypical solutions in non-convex neural networks with discrete and continuous weightscited by 13
  6. 2023Binary perceptrons capacity via fully lifted random duality theorycited by 13
  7. 2019Clustering of solutions in the symmetric binary perceptroncited by 12
  8. 2022Algorithms and Barriers in the Symmetric Binary Perceptron Modelcited by 12
  9. 2023Fl RDT based ultimate lowering of the negative spherical perceptron capacitycited by 11
  10. 2013Entropy landscape of solutions in the binary perceptron problemcited by 10
  11. 2014Local algorithms for independent sets are half-optimalcited by 9
  12. 2019On-Line Balancing of Random Inputscited by 9
  13. 2020Optimization of Mean-field Spin Glassescited by 9
  14. 2021Tight Lipschitz Hardness for Optimizing Mean Field Spin Glassescited by 9
  15. 2024Hardness of sampling solutions from the Symmetric Binary Perceptroncited by 8
  16. 2020Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamicscited by 7
  17. 2014Constructive discrepancy minimization for convex setscited by 6
  18. 2024Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networkscited by 6
  19. 2023Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimizationcited by 5
  20. 2024Discrepancy Algorithms for the Binary Perceptroncited by 5
  21. 2024Some easy optimization problems have the overlap-gap propertycited by 5
  22. 2025Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDTcited by 5
  23. 2025A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energycited by 5
  24. 2023The Algorithmic Phase Transition of Random Graph Alignment Problemcited by 4
  25. 2025CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energycited by 3
  26. 2025Binary perceptron computational gap -- a parametric fl RDT viewcited by 3
  27. 2023Optimization Algorithms for Multi-Species Spherical Spin Glassescited by 1
  28. 2025Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glassescited by 1
  29. 2025Optimal Hardness of Online Algorithms for Large Independent Setscited by 1
  30. 2025Sharp Online Hardness for Large Balanced Independent Setscited by 1
  31. 2026Parametric RDT approach to computational gap of symmetric binary perceptroncited by 1
  32. 2026Stable algorithms cannot reliably find isolated perceptron solutionscited by 1

Built on by

Not cited yet.