# Hardness of sampling solutions from the Symmetric Binary Perceptron

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2024.

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

- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [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)

We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the set of solutions to the symmetric binary perceptron model at any constraint-to-variable density. This result is in contrast to the question of finding a solution to the same problem, where efficient (and stable) algorithms are known to succeed at sufficiently low density. This result suggests that the solutions found efficiently -- whenever this task is possible -- must be highly atypical, and therefore provides an example of a problem where search is efficiently possible but approximate sampling from the set of solutions is not, at least within these two classes of algorithms.