ACT Special Seminar: Parikshit Gopalan/Georgia Tech On Learning Noisy Parities in TAY 3.128

Contact Name: 
Jenna Whitney
Date: 
Jun 27, 2006 2:00pm - 3:00pm

Speaker Name/Affiliation: Parikshit Gopalan/Georg

ia Tech

Talk Title: On Learning Noisy Parities

Date/Time: J

une 27 2006 at 2:00 p.m.

Location: TAY 3.128

Host: Adam K

livans

Talk Abstract:
Learning of parities under the uniform dist

ribution with
random classification noise aka the noisy parity problem
is a
famous open problem in computational learning. We reduce a number

of basic problems regarding learning under the uniform distribution to learning of noisy parities.

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

hash Khot and Ashok Ponnuswami.