# Binary perceptrons capacity via fully lifted random duality theory

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 53 references that are in the map.
- First posted on arXiv 29 Nov 2023.

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

- [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)
- [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)
- [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, 13 of 13)

- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [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)
- [Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper bounds](https://mlsanity.com/paper/2312.08244/) (2023)
- [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)
- [A large deviation view of stationarized fully lifted blirp interpolation](https://mlsanity.com/paper/2506.19273/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

We study the statistical capacity of the classical binary perceptrons with general thresholds kappa. After recognizing the connection between the capacity and the bilinearly indexed (bli) random processes, we utilize a recent progress in studying such processes to characterize the capacity. In particular, we rely on fully lifted random duality theory (fl RDT) established in citeStojnicflrdt23 to create a general framework for studying the perceptrons' capacities. Successful underlying numerical evaluations are required for the framework (and ultimately the entire fl RDT machinery) to become fully practically operational. We present results obtained in that directions and uncover that the capacity characterizations are achieved on the second (first non-trivial) level of stationarized full lifting. The obtained results exactly match the replica symmetry breaking predictions obtained through statistical physics replica methods in citeKraMez89. Most notably, for the famous zero-threshold scenario, kappa=0, we uncover the well known α≈0.8330786 scaled capacity.