| 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.