|COMPUTER SCIENCE/DISCRETE MATH I|
|Topic:||On Hardness of Learning Intersection of Two Halfspaces|
|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.