Stable algorithms cannot reliably find isolated perceptron solutions

Shuyang Gong, Brice Huang, Shuangping Li +1

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 strikin…