Algorithms and Barriers in the Symmetric Binary Perceptron Model

David Gamarnik, Eren C. Kızıldağ, Will Perkins +1

The symmetric binary perceptron ($\text{SBP}$) exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far belo…