### Abstract

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 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 R^{n}, or whether any function of ℓ linear threshold functions can correctly classify at most 1/2+ ε fraction of the points.

Original language | English (US) |
---|---|

Title of host publication | STOC'08 |

Subtitle of host publication | Proceedings of the 2008 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 345-353 |

Number of pages | 9 |

ISBN (Print) | 9781605580470 |

DOIs | |

State | Published - 2008 |

Event | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada Duration: May 17 2008 → May 20 2008 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 |
---|---|

Country | Canada |

City | Victoria, BC |

Period | 5/17/08 → 5/20/08 |

### Keywords

- Approximation
- Halfspaces
- Hardness
- Learning

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'On hardness of learning intersection of two halfspaces'. Together they form a unique fingerprint.

## Cite this

Khot, S., & Saket, R. (2008). On hardness of learning intersection of two halfspaces. In

*STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing*(pp. 345-353). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/1374376.1374426