2015
Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings
Publication
Publication
Presented at the
Annual Symposium on Computational Geometry
We give a 2O(n)(1+1/")n time and poly(n)-space deterministic algorithm for computing a (1+")n
approximation to the volume of a general convex body K, which comes close to matching the
(1+c/")n/2 lower bound for volume estimation in the oracle model by Bárány and Füredi (STOC
1986, Proc. Amer. Math. Soc. 1988). This improves on the previous results of Dadush and
Vempala (Proc. Nat’l Acad. Sci. 2013), which gave the above result only for symmetric bodies
and achieved a dependence of 2O(n)(1 + log5/2(1/")/"3)n.
For our methods, we reduce the problem of volume estimation in K to counting lattice points
in K Rn (via enumeration) for a specially constructed lattice L: a so-called thin covering of
space with respect to K (more precisely, for which L + K = Rn and voln(K)/ det(L) = 2O(n)).
The trade off between time and approximation ratio is achieved by scaling down the lattice.
As our main technical contribution, we give the first deterministic 2O(n)-time and poly(n)-
space construction of thin covering lattices for general convex bodies. This improves on a recent
construction of Alon et al. (STOC 2013) which requires exponential space and only works for
symmetric bodies. For our construction, we combine the use of the M-ellipsoid from convex
geometry (Milman, C. R. Math. Acad. Sci. Paris 1986) together with lattice sparsification and
densification techniques (Dadush and Kun, SODA 2013; Rogers, J. London Math. Soc. 1950).
Additional Metadata | |
---|---|
doi.org/10.4230/LIPIcs.SOCG.2015.704 | |
Annual Symposium on Computational Geometry | |
Organisation | Networks and Optimization |
Dadush, D. (2015). Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings. In Proceedings of Annual Symposium on Computational Geometry 2015 (SoCG 0) (pp. 704–718). doi:10.4230/LIPIcs.SOCG.2015.704 |