Red Points and Blue Points

Abstract: Given points in $n$-dimensional space drawn independently from an arbitrary (unknown) distribution and labeled red or blue so that the colors can be separated by an (unknown) intersection of $k$ halfspaces, can you efficiently compute (learn) a rule to separate the colors?  Avrim posed this question in my first meeting with him 33 years ago, and I've been (happily) struggling with it since. In this talk, I'll describe a simple algorithm with complexity exponential in $\sqrt{n \log(1/\rho) \log k}$, assuming a (soft) margin $\rho$. This improves known results (which are exponential in either $k$ or $1/\rho$) and matches statistical query and cryptographic lower bounds up to the logarithmic factors in $k$ and $1/rho$. 

Joint work with Shyamal Patel.