Abstract
Symmetric binary perceptron model exhibits an interesting phenomena, where the existence of polynomial time algorithms coincides with the presence of an extreme form of the clustering property. The latter means that at every strictly positive constraints to variables ratio, most of the satisfying solutions are singletons separated by large distances.
In order to understand this conundrum and gain an insight into the true algorithmic tractability of this problem, we conduct a different landscape analysis. We establish that the model exhibits a symmetric version of a multi overlap gap property (m-OGP) at some constraints to density ratio, which, as we show, is above the known algorithmic threshold, but strictly below the satisfiability threshold. We show that m-OGP is a barrier to stable algorithms, appropriately defined, and conjecture that the onset of m-OGP coincides with the onset of algorithmic hardness. The proof of this barrier is based on Ramsey theory from extremal combinatorics. The most technically involved part of the work is establishing the stability of the known algorithms, which unlike in several prior models, do not appear to fall into the class of low-degree polynomials.
Joint work with Eren Kizildag, Will Perkins and Changji Xu.