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.