Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model

Avrim Blum, Adam Kalai, Hal Wasserman

We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise. This results in a polynomial-time algorithm for…