# Algorithms and Barriers in the Symmetric Binary Perceptron Model

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

## Key facts

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

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

- [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)
- [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)
- [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)
- [Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms](https://mlsanity.com/paper/2502.16292/) (2025)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [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 symmetric binary perceptron (textttSBP) exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far below the threshold for the existence of solutions. Furthermore, the textttSBP exhibits a striking structural property: at all positive constraint densities almost all of its solutions are 'totally frozen' singletons separated by large Hamming distance citeperkins2021frozen,abbe2021proof. This suggests that finding a solution to the textttSBP may be computationally intractable. At the same time, the textttSBP does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in citebaldassi2020clustering: efficient algorithms succeed in the face of freezing by finding exponentially rare clusters of large size. However, it was discovered recently that such rare large clusters exist at all subcritical densities, even at those well above the limits of known efficient algorithms citeabbe2021binary. Thus the driver of the statistical-to-computational gap exhibited by this model remains a mystery. In this paper, we conduct a different landscape analysis to explain the algorithmic tractability of this problem. We show that at high enough densities the textttSBP exhibits the multi Overlap Gap Property (m-OGP), an intricate geometrical property known to be a rigorous barrier for large classes of algorithms. Our analysis shows that the m-OGP threshold (a) is well below the satisfiability threshold; and (b) matches the best known algorithmic threshold up to logarithmic factors as m→∞. We then prove that the m-OGP rules out the class of stable algorithms for the textttSBP above this threshold. We conjecture that the m → ∞ limit of the m-OGP threshold marks the algorithmic threshold for the problem.