Alexander Munteanu

Terminal Dimension Reduction for Time Series with Applications

Alexander Munteanu, Matteo Russo, David Saulpic, et al.

Hardness of High-Dimensional Linear Classification

Alexander Munteanu, Simon Omlor, Jeff M. Phillips

This paper proves that linear classification (finding the best line/plane to separate data points) requires exponential time in the number of dimensions, closing a major gap in our theoretical understanding of why this problem is fundamentally hard. The researchers connect this difficulty to other hard computational problems and show their results hold under realistic computing constraints where algorithms can only test which side of a line points fall on.