Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings

Abstract

We give a 2^{O(n)}(1+1/eps)^n time and poly(n)-space deterministic algorithm for computing a (1+eps)^n approximation to the volume of a general convex body K, which comes close to matching the (1+c/eps)^{n/2} lower bound for volume estimation in the oracle model by Barany and Furedi (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 2^{O(n)}(1+log^{5/2}(1/eps)/eps^3)^n. 

For our methods, we reduce the problem of volume estimation in K to counting lattice points in K subseteq R^n (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 = R^n and vol_n(K)/det(L) = 2^{O(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 2^{O(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).