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

Abstract

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.

References in corpus (1)

• Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms

Cited by in corpus (5)

• Multitype Integer Monoid Optimization and Applications
• Integer Programming in Parameterized Complexity: Three Miniatures
• Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ${\ell }_p$ norm
• A Deterministic Polynomial Space Construction for eps-nets under any Norm
• An FPTAS for the Volume of a $\mathcal{V}$-polytope ---It is Hard to Compute The Volume of The Intersection of Two Cross-polytopes