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

Author Daniel Dadush



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.704.pdf
  • Filesize: 406 kB
  • 15 pages

Document Identifiers

Author Details

Daniel Dadush

Cite AsGet BibTex

Daniel Dadush. Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 704-718, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.704

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).
Keywords
  • Deterministic Volume Estimation
  • Convex Geometry
  • Lattice Coverings of Space
  • Lattice Point Enumeration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. N. Alon, A. Schraibman, T. Lee, and S. Vempala. The approximate rank of a matrix and its algorithmic applications. In STOC, 2013. Google Scholar
  2. A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In FOCS, pages 459-468, 2006. Google Scholar
  3. A. Becker, N. Gama, and A. Joux. Solving shortest and closest vector problems: The decomposition approach. Cryptology Eprint. Report 2013/685, 2013. Google Scholar
  4. G. J. Butler. Simultaneous packing and covering in euclidean space. Proceedings of the London Mathematical Society, 25(3):721-735, 1972. Google Scholar
  5. D. Dadush. Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation. PhD thesis, Georgia Institute of Technology, 2012. Google Scholar
  6. D. Dadush and G. Kun. Lattice sparsification and the approximate closest vector problem. In SODA, 2013. Google Scholar
  7. D. Dadush, C. Peikert, and S. Vempala. Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In FOCS, 2011. Google Scholar
  8. D. Dadush and S. Vempala. Near-optimal deterministic algorithms for volume computation via m-ellipsoids. Proceedings of the National Academy of Sciences, 2013. Google Scholar
  9. M. E. Dyer, A. M. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1-17, 1991. Preliminary version in STOC 1989. Google Scholar
  10. U. Erez, S. Litsyn, and R. Zamir. Lattices which are good for (almost) everything. IEEE Transactions on Information Theory, 51(10):3401-3416, 2005. Google Scholar
  11. Z. Füredi and I. Bárány. Computing the volume is difficult. In STOC, pages 442-447, New York, NY, USA, 1986. ACM. Google Scholar
  12. Z. Füredi and I. Bárány. Approximation of the sphere by polytopes having few vertices. Proceedings of the AMS, 102(3), 1988. Google Scholar
  13. M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988. Google Scholar
  14. P. M. Gruber. Convex and discrete geometry, volume 336. Springer Science & Business Media, 2007. Google Scholar
  15. B. Grünbaum. Measures of symmetry for convex sets. In Proceedings of the 7th Symposium in Pure Mathematics of the American Mathematical Society, Symposium on Convexity, pages 233-270, 1961. Google Scholar
  16. G. Hanrot and D. Stehlé. Improved analysis of Kannan’s shortest lattice vector algorithm. In CRYPTO, pages 170-186, Berlin, Heidelberg, 2007. Springer-Verlag. Google Scholar
  17. D. Micciancio and P. Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. SIAM Journal on Computing, 42(3):1364-1391, 2013. Preliminary version in STOC 2010. Google Scholar
  18. V. D. Milman. Inégalités de Brunn-Minkowski inverse et applications at la theorie locales des espaces normes. C. R. Math. Acad. Sci. Paris, 302(1):25-28, 1986. Google Scholar
  19. V. D. Milman and A. Pajor. Entropy and asymptotic geometry of non-symmetric convex bodies. Advances in Mathematics, 152(2):314-335, 2000. Google Scholar
  20. C. A. Rogers. Lattice coverings of space: The Minkowski-Hlawka theorem. Proceedings of the London Mathematical Society, s3-8(3):447-465, 1958. Google Scholar
  21. C. A. Rogers. A note on coverings and packings. Journal of the London Mathematical Society, s1-25(4):327-331, 1950. Google Scholar
  22. C. A. Rogers. Lattice coverings of space. Mathematika, 6:33-39, 6 1959. Google Scholar
  23. C. A. Rogers and G. C. Shephard. The difference body of a convex body. Archiv der Mathematik, 8:220-233, 1957. Google Scholar
  24. C. A. Rogers and C. Zong. Covering convex bodies by translates of convex bodies. Mathematika, 44:215-218, 6 1997. Google Scholar
  25. D. B. Yudin and A. S. Nemirovski. Evaluation of the information complexity of mathematical programming problems (in russian). Ekonomika i Matematicheskie Metody, 13(2):3-45, 1976. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail