Preprint
Oct 2026
Near-Optimal Oracle Bounds for Isotropic Rounding
We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower boun...
Yang P. Liu, Richard Peng, Alicia Stepin et al.
· 0 citations