Algorithms and Barriers in the Symmetric Binary Perceptron Model

Understand

The symmetric binary perceptron ($\texttt{SBP}$) 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 $\texttt{SBP}$ exhibits a striking structural property: at all positive constraint densities almost all of its solutions are 'totally frozen' singletons separated by large Hamming distance \cite{perkins2021frozen,abbe2021proof}.
• This suggests that finding a solution to the $\texttt{SBP}$ may be computationally intractable.
• At the same time, the $\texttt{SBP}$ does admit polynomial-time search algorithms at low enough densities.