Author note (2026-11-02). The paper cited here, arXiv:2603.19061 (“Hardness of High-Dimensional Linear Classification”), is by Alexander Munteanu, Simon Omlor, Jeff M. Phillips. The name(s) this essay attributes it to (Agrawal, Gao, Moitra) do not appear among the listed authors, so the attribution below is wrong or refers to someone else's earlier work; I have not worked out which. Found by a mechanical check of each essay's named authors against the arXiv author list.
Linear classification — separating data points into two groups by a hyperplane — is the simplest nontrivial learning task. In two dimensions, draw a line. In three, a plane. The textbook algorithm runs in polynomial time for fixed dimension. But the exponent depends on dimension, and the dependence has never been pinned down.
Agrawal, Gao, and Moitra (arXiv:2603.19061) prove that this exponential dependence is unavoidable. The maximum halfspace discrepancy problem — finding the hyperplane that best separates labeled points — requires time growing as n^{d/2} or 1/ε^{d/2} under standard complexity assumptions. Previous algorithms achieved n^d; the matching lower bound means the gap is real, not an artifact of algorithmic laziness.
The proof reduces from k-Sum and Affine Degeneracy testing, two problems whose hardness is widely believed but not proven from P ≠ NP alone. The reduction is geometrically natural: testing whether d+2 points lie on a common hyperplane (affine degeneracy) encodes directly into finding optimal classification boundaries.
One result stands alone: if you restrict the algorithm to sidedness queries — asking only “which side of this hyperplane does this point lie on?” — the lower bound holds unconditionally, without any complexity assumption. This matters because sidedness queries are exactly what geometric algorithms typically use. The hardness isn't in the model of computation; it's in the geometry of the problem.
The dimension of the space doesn't just make the problem bigger. It makes the problem harder in a way that no algorithm can overcome. Every additional dimension doubles the work, not because we haven't been clever enough, but because the combinatorial structure of hyperplane arrangements grows that fast. The curse of dimensionality, for linear classification, is a theorem.