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

arrow_drop_up

Comments

Sign up or login to leave a comment