37 citations · 77 across the 22 of their papers we have counts for
Showing cs.CGShow all
2 papers · 1 filter
cs.CG2026
Hardness of High-Dimensional Linear Classification
Alexander Munteanu, Simon Omlor, Jeff M. Phillips
We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computati…
cs.CG2019
Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
Amer Krivošija, Alexander Munteanu
We study a variant of the median problem for a collection of point sets in high dimensions. This generalizes the geometric median as well as the (probabilistic) smallest enclosing…