mlsanityData to 14 Oct 2026

Learning Functions of Halfspaces

arXiv 2603.08700 ↗First posted 9 Mar 2026cs.DS cs.CCcited by 2

Not on the map. Why?

Abstract (arXiv)

We give an algorithm that learns arbitrary Boolean functions of k arbitrary halfspaces over ℝ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 2o(n).

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). First posted on arXiv 9 Mar 2026.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Tight Bounds for Learning Polyhedra with a Margincited by 0
  2. 2026Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginalscited by 0