COMPUTER SCIENCE/DISCRETE MATH I | |

Topic: | On Hardness of Learning Intersection of Two Halfspaces |

Speaker: | Subhash Khot |

Affiliation: | Courant Institute, New York University |

Date: | Monday, November 26 |

Time/Room: | 11:15am - 12:15pm/West Building Lecture Theatre |

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.