# Hardness of High-Dimensional Linear Classification

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 56 references that are in the map.
- First posted on arXiv 19 Mar 2026.

## Builds on (most cited first, 21 of 21)

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Approximate Sparse Linear Regression](https://mlsanity.com/paper/1609.08739/) (2016)
- [Tight Hardness Results for Maximum Weight Rectangles](https://mlsanity.com/paper/1602.05837/) (2016)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Computing Approximate Statistical Discrepancy](https://mlsanity.com/paper/1804.11287/) (2018)
- [Theorems of Carath'eodory, Helly, and Tverberg without dimension](https://mlsanity.com/paper/1806.08725/) (2018)
- [Probabilistic smallest enclosing ball in high dimensions via subgradient sampling](https://mlsanity.com/paper/1902.10966/) (2019)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Exact Weight Subgraphs and the k-Sum Conjecture](https://mlsanity.com/paper/1304.7558/) (2013)
- [Scalable Spatial Scan Statistics for Trajectories](https://mlsanity.com/paper/1906.01693/) (2019)
- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [Computational Complexity in Property Testing](https://mlsanity.com/paper/2510.05927/) (2025)
- [A Simple Algorithm for Maximum Margin Classification, Revisited](https://mlsanity.com/paper/1507.01563/) (2015)
- [No-dimensional Tverberg Theorems and Algorithms](https://mlsanity.com/paper/1907.04284/) (2019)
- [Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees](https://mlsanity.com/paper/2111.03744/) (2021)
- [Improved Algebraic Degeneracy Testing](https://mlsanity.com/paper/2212.03030/) (2022)
- [No-dimensional Tverberg Partitions Revisited](https://mlsanity.com/paper/2306.01678/) (2023)

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

- [Dimension Reduction for Curves: Simplified and Generalized](https://mlsanity.com/paper/2607.03112/) (2026)

## Abstract (arXiv)

We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms. However, only O(nd) and respectively tilde O(1/varepsilond) upper bounds are known and complemented by polynomial lower bounds that do not support the exponential in dimension dependence. We close this gap up to polylogarithmic terms by reduction from widely-believed hardness conjectures for Affine Degeneracy testing and k-Sum problems. Our reductions yield matching lower bounds of tildeOmega(nd) and respectively tildeOmega(1/varepsilond) based on Affine Degeneracy testing, and tildeOmega(nd/2) and respectively tildeOmega(1/varepsilond/2) conditioned on k-Sum. The first bound also holds unconditionally if the computational model is restricted to make sidedness queries, which corresponds to a widely spread setting implemented and optimized in many contemporary algorithms and computing paradigms.