Near-Optimal Deterministic Algorithms for Volume Computation and Lattice Problems via M-Ellipsoids

Daniel Dadush, Santosh Vempala

We give a deterministic 2^{O(n)} algorithm for computing an M-ellipsoid of a convex body, matching a known lower bound. This has several interesting consequences including improved deterministic algorithms for volume estimation of convex bodies and the shortest and closest lattice vector problems under general norms.

Knowledge Graph



Sign up or login to leave a comment