On Hardness of Learning Intersection of Two Halfspaces

COMPUTER SCIENCE/DISCRETE MATH I
Topic:On Hardness of Learning Intersection of Two Halfspaces
Speaker:Subhash Khot
Affiliation:Courant Institute, New York University
Date:Monday, November 26
Time/Room:11:15am - 12:15pm/West Building Lecture Theatre

I will present a result that shows hardness of weak PAC-learning intersection of two halfspaces using a hypothesis which is an intersection of k halfspaces for any (fixed) integer k. Specifically, for every integer k and an arbitrarily small constant \eps > 0, unless NP = RP, no polynomial time algorithm can distinguish whether there is an intersection of two halfspaces that correctly classifies a given set of labelled points in R^n, or whether any intersection of k halfspaces can correctly classify at most 1/2+\eps fraction of the points. Joint work with Rishi Saket.