Computer Science/Discrete Mathematics Seminar I

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.