I will present some recent hardness results for learning important
concept classes such as noisy halfspaces, noisy monomials, and
intersection of two halfspaces. For each of the three problems, even
weak PAC-learning turns out to be NP-hard. I will also present a
related result showing that learning "k-juntas" reduces to learning
noisy parity under uniform distribution.
Based on joint works with [Feldman Gopalan Ponnuswami FOCS'06] and
[Saket STOC'08].
The first paper is available at:
http://www.cc.gatech.edu/~pashok/research.html
Rishi Saket will be presenting the second paper in Theory Seminar on
Thu, Feb 28,
at 2:15-3:15PM, WWH-1314.