Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, Rocco A. Servedio
Abstract
We give an algorithm that learns arbitrary Boolean functions of k arbitrary halfspaces over R n , in the challenging distribution-free Probably Approximately Correct (PAC) learning model, running in time 2 √ n•(log n) O(k) . This is the first algorithm that can PAC learn even intersections of two halfspaces in time 2 o(n) .
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Distribution-free Testing for Halfspaces (Almost) Requires PAC LearningXi Chen, Shyamal PatelSODA 2022 · 2 citations
- DNF Learning via Locally Mixing Random WalksJosh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. ServedioSTOC 2025
- A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning ConjunctionsXi Chen, Shyamal Patel, Rocco A. ServedioSTOC 2026 · 4 citations
- Hardness of learning DNFs using halfspacesSuprovat Ghoshal, Rishi SaketSTOC 2021
- Distribution-Free Testing of Decision Lists with a Sublinear Number of QueriesXi Chen, Yumou Fei, Shyamal PatelSTOC 2024
