Red Points and Blue Points

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$ half-spaces, can you efficiently compute (learn) a rule to separate the colors? Santosh Vempala (Georgia Tech) describes a simple algorithm with complexity exponential in $\sqrt{n \log(1/\rho) \log k}$, assuming a (soft) margin $\rho$. This improves on 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$.