# Binary perceptron computational gap -- a parametric fl RDT view

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 98 references that are in the map.
- First posted on arXiv 2 Nov 2025.

## Builds on (most cited first, 30 of 37)

- [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)
- [Unveiling the structure of wide flat minima in neural networks](https://mlsanity.com/paper/2107.01163/) (2021)
- [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)
- [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)

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

- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)
- [Precise sample covariance spectral norm error -- an RDT view](https://mlsanity.com/paper/2607.14460/) (2026)

## Abstract (arXiv)

Recent studies suggest that asymmetric binary perceptron (ABP) likely exhibits the so-called statistical-computational gap characterized with the appearance of two phase transitioning constraint density thresholds: textbf(i) the satisfiability threshold αc, below/above which ABP succeeds/fails to operate as a storage memory; and textbf(ii) algorithmic threshold αa, below/above which one can/cannot efficiently determine ABP's weight so that it operates as a storage memory. We consider a particular parametric utilization of fully lifted random duality theory (fl RDT) [85] and study its potential ABP's algorithmic implications. A remarkable structural parametric change is uncovered as one progresses through fl RDT lifting levels. On the first two levels, the so-called c sequence -- a key parametric fl RDT component -- is of the (natural) decreasing type. A change of such phenomenology on higher levels is then connected to the αc -- αa threshold change. Namely, on the second level concrete numerical values give for the critical constraint density α=αc≈ 0.8331. While progressing through higher levels decreases this estimate, already on the fifth level we observe a satisfactory level of convergence and obtain α≈ 0.7764. This allows to draw two striking parallels: textbf(i) the obtained constraint density estimate is in a remarkable agrement with range α∈ (0.77,0.78) of clustering defragmentation (believed to be responsible for failure of locally improving algorithms) [17,88]; and textbf(ii) the observed change of c sequence phenomenology closely matches the one of the negative Hopfield model for which the existence of efficient algorithms that closely approach similar type of threshold has been demonstrated recently [87].