The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with a fixed intercept. The computational landscape of the binary perceptron is not yet well-understood. In some regimes there may be an information-computation gap, but there is much room for improvement on both the algorithms and lower-bounds side. In this talk I will discuss a forthcoming work in which we analyze the performance of canonical discrepancy minimization algorithms for the binary perceptron problem, obtaining new algorithmic results with simple off-the-shelf algorithms and relatively simple analysis. In some settings, we complement these algorithmic results with (close, but non-matching) overlap-gap lower bounds.
This is based on joint work with Shuangping Li and Kangjie Zhou.