CMX Lunch Seminar

We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A striking feature of this model is that at every positive constraint density, it is expected that a 1 - o_N(1) fraction of solutions are strongly isolated, i.e. separated from all others by Hamming distance Omega(N). At the same time, efficient algorithms are known to find solutions at certain positive constraint densities. This raises a natural question: can any isolated solution be algorithmically visible?

We answer this in the negative: no algorithm whose output is stable under a tiny Gaussian resampling of the disorder can reliably locate isolated solutions. We show that any stable algorithm has success probability at most (3 sqrt(17) - 9)/4 + o_N(1) <= 0.84233. Furthermore, every stable algorithm that finds a solution with probability 1 - o_N(1) finds an isolated solution with probability o_N(1).

The class of stable algorithms we consider includes degree-D polynomials up to D <= o(N/log N); under the low-degree heuristic, this suggests that locating strongly isolated solutions requires running time exp(Theta-tilde(N)).

Our proof does not use the overlap gap property. Instead, we show via Pitt's correlation inequality that after a random perturbation of the disorder, the number of solutions located close to a pre-existing isolated solution cannot concentrate at 1.

This is based on joint work with Shuyang Gong, Brice Huang, and Mark Sellke.