# Parametric RDT approach to computational gap of symmetric binary perceptron

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 112 references that are in the map.
- First posted on arXiv 15 Jan 2026.

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

- [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)
- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [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)
- [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)
- [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)
- [Spherical perceptron as a storage memory with limited errors](https://mlsanity.com/paper/1306.3809/) (2013)
- [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)
- [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)

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

- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

We study potential presence of statistical-computational gaps (SCG) in symmetric binary perceptrons (SBP) via a parametric utilization of fully lifted random duality theory (fl-RDT) [96]. A structural change from decreasingly to arbitrarily ordered c-sequence (a key fl-RDT parametric component) is observed on the second lifting level and associated with satisfiability (αc) -- algorithmic (αa) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap SCG=αc-αa. The second level estimate is shown to match the theoretical αc whereas the rrightarrow ∞ level one is proposed to correspond to αa. For example, for the canonical SBP (kappa=1 margin) we obtain αc≈ 1.8159 on the second and αa≈ 1.6021 (with converging tendency towards ~ 1.59 range) on the seventh level. Our propositions remarkably well concur with recent literature: (i) in [20] local entropy replica approach predicts αLE≈ 1.58 as the onset of clustering defragmentation (presumed driving force behind locally improving algorithms failures); (ii) in αrightarrow 0 regime we obtain on the third lifting level kappa≈ 1.2385√fracαa-logleft ( αa right )  which qualitatively matches overlap gap property (OGP) based predictions of [43] and identically matches local entropy based predictions of [24]; (iii) c-sequence ordering change phenomenology mirrors the one observed in asymmetric binary perceptron (ABP) in [98] and the negative Hopfield model in [100]; and (iv) as in [98,100], we here design a CLuP based algorithm whose practical performance closely matches proposed theoretical predictions.