Title : On Hardness of Learning Intersection of Two Halfspaces.

Speaker : Rishi Saket (Georgia Tech, visiting NYU)

Abstract: 

Learning intersections of halfspaces is a well studied problem in 
learning theory. It is known that it is hard to PAC-learn intersections 
of two halfspaces using a hypothesis of intersection of constant number 
halfspaces[ABFKP 04]. We show that, unless NP=RP, it is hard to (even) 
weakly PAC-learn intersection of two halfspaces in R^n using a 
hypothesis which is an intersection of \ell halfspaces for any integer 
\ell. Specifically, we show that for every integer \ell 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 labeled points in 
R^n, or whether any intersection of \ell halfspaces can correctly 
classify at most 1/2 + \eps fraction of the points.

Joint Work with Subhash Khot.