Discrepancy Algorithms for the Binary Perceptron

Shuangping Li, Tselil Schramm, Kangjie Zhou

The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with intercept $-\kappa$. We analyze the performance of the can…