On Agnostic Learning of Parities, Monomials and Halfspaces

The paper shows that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al. [BKW03], this gives the first nontrivial algorithm for agnostic learning of parities. The paper uses similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, it shows that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables.