Harvard Theory of Computation Seminar
New Results for Learning Noisy Parities and Halfspaces
Subhash Khot, Georgia Tech
Place and Time: Monday 5/15, Maxwell-Dworkin 319
Refreshments at 2:30, talk at 2:45.
ABSTRACT
I will present some new results on the learnability of
parities
and halfspaces in the presence of noise. The results can be
informally
stated as:
(1) In uniform distribution setting, learning juntas on k
variables
recuces to learning noisy parities on k variables. Learning
DNFs
reduces to learning noisy parities on O(log n) variables.
(2) Learning halfspaces: Given a set of labeled examples in R^n
such
that there is a halfspace that correctly classifies 1-\eps
fraction
of examples, it is NP-hard to find a halfspace that is correct
on
1/2+\eps fraction of examples for any \eps > 0. This is
optimal.
(3) It is hard to PAC-learn majorities of halfspaces assuming that
the Ajtai-Dwork lattice-based cryptosystem is secure (which
amounts
to assuming that the shortest vector problem for n-dimensional
lattices is hard to approximate within factor n^{O(1)}).
Joint work with Vitaly Feldman, Parikshit Gopalan, and Ashok
Kumar
Ponnuswami.