# Origin of the computational hardness for learning with binary synapses

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2014.

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

- [Learning through atypical "phase transitions" in overparameterized neural networks](https://mlsanity.com/paper/2110.00683/) (2021)
- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024)
- [Statistical mechanics of continual learning: variational principle and mean-field potential](https://mlsanity.com/paper/2212.02846/) (2022)
- [Eight challenges in developing theory of intelligence](https://mlsanity.com/paper/2306.11232/) (2023)
- [Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks](https://mlsanity.com/paper/2410.06717/) (2024)
- [Nonequilbrium physics of generative diffusion models](https://mlsanity.com/paper/2405.11932/) (2024)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (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)
- [Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems](https://mlsanity.com/paper/2111.13302/) (2021)
- [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)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

Supervised learning in a binary perceptron is able to classify an extensive number of random patterns by a proper assignment of binary synaptic weights. However, to find such assignments in practice, is quite a nontrivial task. The relation between the weight space structure and the algorithmic hardness has not yet been fully understood. To this end, we analytically derive the Franz-Parisi potential for the binary preceptron problem, by starting from an equilibrium solution of weights and exploring the weight space structure around it. Our result reveals the geometrical organization of the weight spacetextemdash the weight space is composed of isolated solutions, rather than clusters of exponentially many close-by solutions. The point-like clusters far apart from each other in the weight space explain the previously observed glassy behavior of stochastic local search heuristics.