Hardness of High-Dimensional Linear Classification

Alexander Munteanu, Simon Omlor, Jeff M. Phillips

We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computati…