# Algorithmic pure states for the negative spherical perceptron

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2020.

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

- [Gaussian Universality of Perceptrons with Random Labels](https://mlsanity.com/paper/2205.13303/) (2022)
- [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)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)
- [Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks](https://mlsanity.com/paper/2410.06717/) (2024)
- [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)
- [High-dimensional manifold of solutions in neural networks: insights from statistical physics](https://mlsanity.com/paper/2309.09240/) (2023)
- [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)

We consider the spherical perceptron with Gaussian disorder. This is the set S of points σ ∈ ℝN on the sphere of radius √N satisfying langle ga , σ rangle ≥ kappa√N, for all 1 ≤ a ≤ M, where (ga)a=1M are independent standard gaussian vectors and kappa ∈ ℝ is fixed. Various characteristics of S such as its surface measure and the largest M for which it is non-empty, were computed heuristically in statistical physics in the asymptotic regime N → ∞, M/N → α. The case kappa<0 is of special interest as S is conjectured to exhibit a hierarchical tree-like geometry known as "full replica-symmetry breaking" (FRSB) close to the satisfiability threshold αSAT(kappa), and whose characteristics are captured by a Parisi variational principle akin to the one appearing in the Sherrington-Kirkpatrick model. In this paper we design an efficient algorithm which, given oracle access to the solution of the Parisi variational principle, exploits this conjectured FRSB structure for kappa<0 and outputs a vector hatσ satisfying langle ga , hatσrangle ≥ kappa √N for all 1≤ a ≤ M and lying on a sphere of non-trivial radius √barq N, where barq ∈ (0,1) is the right-end of the support of the associated Parisi measure. We expect hatσ to be approximately the barycenter of a pure state of the spherical perceptron. Moreover we expect that barq → 1 as α → αSAT(kappa), so that biglangle ga,hatσ/|hatσ|bigrangle ≥ (kappa-o(1))√N near criticality.