# Fl RDT based ultimate lowering of the negative spherical perceptron capacity

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 45 references that are in the map.
- First posted on arXiv 27 Dec 2023.

## Builds on (most cited first, 15 of 15)

- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [Another look at the Gardner problem](https://mlsanity.com/paper/1306.3979/) (2013)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [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)
- [Discrete perceptrons](https://mlsanity.com/paper/1306.4375/) (2013)
- [Lifting ℓ1-optimization strong and sectional thresholds](https://mlsanity.com/paper/1306.3770/) (2013)
- [Lifting/lowering Hopfield models ground state energies](https://mlsanity.com/paper/1306.3975/) (2013)
- [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)
- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Tractability from overparametrization: The example of the negative perceptron](https://mlsanity.com/paper/2110.15824/) (2021)
- [Algorithms and Barriers in the Symmetric Binary Perceptron Model](https://mlsanity.com/paper/2203.15667/) (2022)
- [Spherical perceptron as a storage memory with limited errors](https://mlsanity.com/paper/1306.3809/) (2013)
- [Box constrained ℓ1 optimization in random linear systems -- asymptotics](https://mlsanity.com/paper/1612.06835/) (2016)

## Built on by (most cited first, 11 of 11)

- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [Injectivity capacity of ReLU gates](https://mlsanity.com/paper/2410.20646/) (2024)
- [Deep ReLU networks -- injectivity capacity upper bounds](https://mlsanity.com/paper/2412.19677/) (2024)
- [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Capacity of the Hebbian-Hopfield network associative memory](https://mlsanity.com/paper/2403.01907/) (2024)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Exact objectives of random linear programs and mean widths of random polyhedrons](https://mlsanity.com/paper/2403.03637/) (2024)
- [Theoretical limits of descending ℓ0 sparse-regression ML algorithms](https://mlsanity.com/paper/2410.07651/) (2024)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

We consider the classical spherical perceptrons and study their capacities. The famous zero-threshold case was solved in the sixties of the last century (see, citeWendel62,Winder,Cover65) through the high-dimensional combinatorial considerations. The general threshold, kappa, case though turned out to be much harder and stayed out of reach for the following several decades. A substantial progress was then made in citeSchTir02 and citeStojnicGardGen13 where the positive threshold (kappa≥ 0) scenario was finally fully settled. While the negative counterpart (kappa≤ 0) remained out of reach, citeStojnicGardGen13 did show that the random duality theory (RDT) is still powerful enough to provide excellent upper bounds. Moreover, in citeStojnicGardSphNeg13, a partially lifted RDT variant was considered and it was shown that the upper bounds of citeStojnicGardGen13 can be lowered. After recent breakthroughs in studying bilinearly indexed (bli) random processes in citeStojnicsflgscompyx23,Stojnicnflgscompyx23, fully lifted random duality theory (fl RDT) was developed in citeStojnicflrdt23. We here first show that the negative spherical perceptrons can be fitted into the frame of the fl RDT and then employ the whole fl RDT machinery to characterize the capacity. To be fully practically operational, the fl RDT requires a substantial numerical work. We, however, uncover remarkable closed form analytical relations among key lifting parameters. Such a discovery enables performing the needed numerical calculations to obtain concrete capacity values. We also observe that an excellent convergence (with the relative improvement ~ 0.1%) is achieved already on the third (second non-trivial) level of the stationarized full lifting.