Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, Rocco A. Servedio
2026Year
3Citations
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 about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
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
