# Learning Functions of Halfspaces

arXiv: https://arxiv.org/abs/2603.08700 · HTML: https://mlsanity.com/paper/2603.08700/

## Key facts

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

## Built on by (most cited first, 2 of 2)

- [Tight Bounds for Learning Polyhedra with a Margin](https://mlsanity.com/paper/2604.14614/) (2026)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## 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).