Lune

STOC2026Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace LearningIlias Diakonikolas, Christos Tzamos, Daniel M. KaneSTOC 2023 · 1 citation
  2. On the Complexity of PAC Learning in Hilbert SpacesSergei ChubanovAAAI 2023 · 1 citation

Related papers

  1. Distribution-free Testing for Halfspaces (Almost) Requires PAC LearningXi Chen, Shyamal PatelSODA 2022 · 2 citations
  2. DNF Learning via Locally Mixing Random WalksJosh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. ServedioSTOC 2025
  3. A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning ConjunctionsXi Chen, Shyamal Patel, Rocco A. ServedioSTOC 2026 · 4 citations
  4. Hardness of learning DNFs using halfspacesSuprovat Ghoshal, Rishi SaketSTOC 2021
  5. Distribution-Free Testing of Decision Lists with a Sublinear Number of QueriesXi Chen, Yumou Fei, Shyamal PatelSTOC 2024
Dusk over the sea between two cliffs drawn in fine vertical lines