TIME: 1:30-2:20 pm,  April 17, 2007


TITLE: Reductions to the noisy parity problem

SPEAKER: Parikshit Gopalan
         University of Washington

The problem of learning parity functions on the Boolean hypercube from
random examples in the presence of random classification noise (aka
the noisy parity problem) is a notorious open problem in computational
learning. The best algorithm known to date due to Blum, Kalai and
Wasserman runs in time 2^{n/log n}. This problem is widely believed to
be hard.

We show that a number of central problems in uniform distribution
learning on the hypercube such as learning juntas, decision trees and
DNFs are reducible to the noisy parity problem.  For instance, the
problem of learning k-juntas reduces to learning a noisy parity of k
unknown variables. This gives evidence in favor of the commonly held
belief that noisy parity is a hard problem.

On the positive side, we use the same techniques to show that the
problem of learning parity function with adversarial noise reduces to
learning parity with random noise. Together with BKW, this gives the
first non-trivial algorithm for this harder noise model.

Based on joint work with Vitaly Feldman, Subhash Khot and Ashok Ponnuswami.