Cover Image

Hardness of High-Dimensional Linear Classification

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Munteanu, Alexander, Omlor, Simon, Phillips, Jeff M.
Format:	Preprint
Published:	2026
Subjects:	Computational Geometry Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Dimension-Free Sampling for Regularized Classification
by: Alishahi, Meysam, et al.
Published: (2026)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
by: Munteanu, Alexander, et al.
Published: (2024)

Turnstile $\ell_p$ leverage score sampling with applications
by: Munteanu, Alexander, et al.
Published: (2024)

Scalable Learning of Multivariate Distributions via Coresets
by: Ding, Zeyu, et al.
Published: (2026)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
by: Krivošija, Amer, et al.
Published: (2025)

Graph-Based Nearest-Neighbor Search without the Spread
by: Giliberti, Jeff, et al.
Published: (2026)

Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
by: Diwan, Haya, et al.
Published: (2024)

Data subsampling for Poisson regression with pth-root-link
by: Lie, Han Cheng, et al.
Published: (2024)

Fast Agnostic Learners in the Plane
by: Eden, Talya, et al.
Published: (2025)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Coresets for Clustering Under Stochastic Noise
by: Huang, Lingxiao, et al.
Published: (2025)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

A Query-Driven Approach to Space-Efficient Range Searching
by: Fotakis, Dimitris, et al.
Published: (2025)

Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
by: Fang, Ziyi, et al.
Published: (2025)

Terminal Embeddings in Sublinear Time
by: Cherapanamjeri, Yeshwanth, et al.
Published: (2021)

Scalable Learning of Item Response Theory Models
by: Frick, Susanne, et al.
Published: (2024)

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
by: Depian, Thomas, et al.
Published: (2025)

Min-1-Planarity is NP-Hard
by: Okada, Yuto
Published: (2026)

A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
by: Gusain, Rachana, et al.
Published: (2025)

Computational Hardness of Private Coreset
by: Ghazi, Badih, et al.
Published: (2026)

On Approximability of $\ell_2^2$ Min-Sum Clustering
by: S., Karthik C., et al.
Published: (2024)

Impossibility of Depth Reduction in Explainable Clustering
by: Deng, Chengyuan, et al.
Published: (2023)

Optimal Orthogonal Drawings in Linear Time
by: Didimo, Walter, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Bin Packing
by: Kar, Debajyoti, et al.
Published: (2025)

Ortho-Radial Drawing in Near-Linear Time
by: Chang, Yi-Jun
Published: (2023)

Exact Algorithms for Clustered Planarity with Linear Saturators
by: Da Lozzo, Giordano, et al.
Published: (2024)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
by: Kar, Debajyoti, et al.
Published: (2026)

Hardness of Median and Center in the Ulam Metric
by: Fischer, Nick, et al.
Published: (2025)

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
by: Cabello, Sergio, et al.
Published: (2021)

Improved Hardness of Approximation for Geometric Bin Packing
by: Ray, Arka, et al.
Published: (2023)

Fitting trees to $\ell_1$-hyperbolic distances
by: Yim, Joon-Hyeok, et al.
Published: (2024)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
by: Conradi, Jacobus, et al.
Published: (2026)

Correcting Underrepresentation and Intersectional Bias for Classification
by: Diana, Emily, et al.
Published: (2023)

Unfairly Splitting Separable Necklaces
by: Schnider, Patrick, et al.
Published: (2024)

Tokenisation over Bounded Alphabets is Hard
by: Kastreva, Violeta, et al.
Published: (2025)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

High-dimensional Linear Bandits with Knapsacks
by: Ma, Wanteng, et al.
Published: (2023)