# Discrete perceptrons

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2013.

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

- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [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)
- [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)
- [Injectivity capacity of ReLU gates](https://mlsanity.com/paper/2410.20646/) (2024)
- [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)
- [Ridge interpolators in correlated factor regression models -- exact risk analysis](https://mlsanity.com/paper/2406.09183/) (2024)
- [Precise analysis of ridge interpolators under heavy correlations -- a Random Duality Theory view](https://mlsanity.com/paper/2406.09199/) (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)

Perceptrons have been known for a long time as a promising tool within the neural networks theory. The analytical treatment for a special class of perceptrons started in seminal work of Gardner citeGar88. Techniques initially employed to characterize perceptrons relied on a statistical mechanics approach. Many of such predictions obtained in citeGar88 (and in a follow-up citeGarDer88) were later on established rigorously as mathematical facts (see, e.g. citeSchTir02,SchTir03,TalBook,StojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13). These typically related to spherical perceptrons. A lot of work has been done related to various other types of perceptrons. Among the most challenging ones are what we will refer to as the discrete perceptrons. An introductory statistical mechanics treatment of such perceptrons was given in citeGutSte90. Relying on results of citeGar88, citeGutSte90 characterized many of the features of several types of discrete perceptrons. We in this paper, consider a similar subclass of discrete perceptrons and provide a mathematically rigorous set of results related to their performance. As it will turn out, many of the statistical mechanics predictions obtained for discrete predictions will in fact appear as mathematically provable bounds. This will in a way emulate a similar type of behavior we observed in citeStojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13 when studying spherical perceptrons.