# Ultrametric OGP - parametric RDT symmetric binary perceptron connection

arXiv: https://arxiv.org/abs/2604.19712 · HTML: https://mlsanity.com/paper/2604.19712/

## 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 (most cited first, 30 of 44)

- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015)
- [Another look at the Gardner problem](https://mlsanity.com/paper/1306.3979/) (2013)
- [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems](https://mlsanity.com/paper/1511.05634/) (2015)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [Fully lifted random duality theory](https://mlsanity.com/paper/2312.00070/) (2023)
- [Origin of the computational hardness for learning with binary synapses](https://mlsanity.com/paper/1408.1784/) (2014)
- [Optimal Low-Degree Hardness of Maximum Independent Set](https://mlsanity.com/paper/2010.06563/) (2020)
- [Discrete perceptrons](https://mlsanity.com/paper/1306.4375/) (2013)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [Algorithmic pure states for the negative spherical perceptron](https://mlsanity.com/paper/2010.15811/) (2020)
- [Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster](https://mlsanity.com/paper/2111.03084/) (2021)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Clustering of solutions in the symmetric binary perceptron](https://mlsanity.com/paper/1911.06756/) (2019)
- [Algorithms and Barriers in the Symmetric Binary Perceptron Model](https://mlsanity.com/paper/2203.15667/) (2022)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Entropy landscape of solutions in the binary perceptron problem](https://mlsanity.com/paper/1304.2850/) (2013)
- [Local algorithms for independent sets are half-optimal](https://mlsanity.com/paper/1402.0485/) (2014)
- [On-Line Balancing of Random Inputs](https://mlsanity.com/paper/1903.06898/) (2019)
- [Optimization of Mean-field Spin Glasses](https://mlsanity.com/paper/2001.00904/) (2020)
- [Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses](https://mlsanity.com/paper/2110.07847/) (2021)
- [Hardness of sampling solutions from the Symmetric Binary Perceptron](https://mlsanity.com/paper/2407.16627/) (2024)
- [Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics](https://mlsanity.com/paper/2004.12063/) (2020)
- [Constructive discrepancy minimization for convex sets](https://mlsanity.com/paper/1404.0339/) (2014)
- [Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks](https://mlsanity.com/paper/2410.06717/) (2024)

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