We show that under the uniform dist

ribution learning parities
with adversarial classification noise reduc

es to learning parities
with random classification noise. Composed wit

h an algorithm of Blum
Kalai and Wasserman this gives the first nontr

ivial algorithm for
learning parities with adversarial noise. We show t

hat learning of DNFs reduces to learning noisy parities of just log n varia

bles and learning k-juntas reduces to learning noisy parities of k variabl

es. These reductions work even in the presence of random classification noi

se in the original DNF or junta.

Joint work with Vitaly Feldman Sub