We study the problem of learning halfspaces in the malicious noise model of Valiant. In this model, an adversary can corrupt an $\eta$ fraction of both the label part and the feature part of an example. We design a polynomial-time algorithm for learning halfspaces in $\Re^d$ under the uniform distribution with near information-theoretic optimal noise tolerance.

Our results also imply the first active learning algorithm for learning halfspaces that can handle malicious noise.

Joint work with Nina Balcan and Phil Long.