@inproceedings{26c29a1ee1904ce19d7ce0c3dca10a09,

title = "On hardness of learning intersection of two halfspaces",

abstract = "We show that unless NP = RP, it is hard to (even) weakly PAC-learn intersection of two halfspaces in Rn using a hypothesis which is a, function of up to ℓ linear threshold functions for any integer ℓ. Specifically, we show that for every integer ℓ and an arbitrarily small constant ε > 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 Rn, or whether any function of ℓ linear threshold functions can correctly classify at most 1/2+ ε fraction of the points.",

keywords = "Approximation, Halfspaces, Hardness, Learning",

author = "Subhash Khot and Rishi Saket",

year = "2008",

doi = "10.1145/1374376.1374426",

language = "English (US)",

isbn = "9781605580470",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "345--353",

booktitle = "STOC'08",

note = "40th Annual ACM Symposium on Theory of Computing, STOC 2008 ; Conference date: 17-05-2008 Through 20-05-2008",

}