Abstract
We look at the computational problem of learning halfspaces under various noise models. In particular, we prove new lower bounds in the statistical query model for learning a halfspace to small error even when the optimal error is very small.