# Discrepancy Algorithms for the Binary Perceptron

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2024.

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

- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [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)

The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with intercept -kappa. We analyze the performance of the canonical discrepancy minimization algorithms of Lovett-Meka and Rothvoss/Eldan-Singh for the asymmetric binary perceptron problem. We obtain new algorithmic results in the kappa = 0 case and in the large-|kappa| case. In the kappa→-∞ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound.