@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",
}