[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On compact representations of Voronoi cells of lattices

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364–1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using coefficients that are bounded by c in absolute value. Given such a basis, we get a polynomial space algorithm for CVP whose running time naturally depends on c. Thus, our main focus is the behavior of the smallest possible value of c, with the following results: there always exist c-compact bases, where c is bounded by \(n^2\) for an n-dimensional lattice; there are lattices not admitting a c-compact basis with c growing sublinearly with the dimension; and every lattice with a zonotopal Voronoi cell has a 1-compact basis.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Engel et al. [11] claim that they computed \(\chi (D_4) = 1\), which turns out to be wrong.

  2. At the time of writing there is no preprint available (personal communication with Frank Vallentin).

References

  1. Aggarwal, D., Stephens-Davidowitz, N.: Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP). In: 1st Symposium on Simplicity in Algorithms (SOSA 2018), OpenAccess Series in Informatics (OASIcs), vol. 61, pp. 12:1–12:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2018)

  2. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of Thirty-Third annual ACM Symposium on Theory of Computing, pp. 601–610. ACM (2001)

  3. Ajtai, M., Kumar, R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: Proceedings of 17th IEEE Annual Conference on Computational Complexity, pp. 53–57. IEEE (2002)

  4. Banaszczyk, W.: Inequalities for convex bodies and polar reciprocal lattices in \(\mathbf{R}^n\). II. Application of \(K\)-convexity. Discrete Comput. Geom. 16(3), 305–311 (1996)

    Article  MathSciNet  Google Scholar 

  5. Bonifas, N., Dadush, D.: Short paths on the Voronoi graph and closest vector problem with preprocessing. In: Proceedings of Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 295–314. SIAM, Philadelphia (2015)

  6. Bost, J.B., Künnemann, K.: Hermitian vector bundles and extension groups on arithmetic schemes. I. Geometry of numbers. Adv. Math. 223(3), 987–1106 (2010)

    Article  MathSciNet  Google Scholar 

  7. Conway, J.H., Sloane, N.J.A.: Low-dimensional lattices. VI. Voronoĭ reduction of three-dimensional lattices. Proc. R. Soc. Lond. Ser. A 436(1896), 55–68 (1992)

    Article  Google Scholar 

  8. Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 290, 3rd edn. Springer, New York (1999)

    Google Scholar 

  9. Dutour Sikirić, M., Grishukhin, V., Magazinov, A.: On the sum of a parallelotope and a zonotope. Eur. J. Comb. 42, 49–73 (2014)

    Article  MathSciNet  Google Scholar 

  10. Engel, P.: Mathematical problems in modern crystallography. Comput. Math. Appl. 16(5–8), 425–436 (1988)

    Article  MathSciNet  Google Scholar 

  11. Engel, P., Michel, L., Senechal, M.: New geometric invariants for Euclidean lattices. In: Réseaux euclidiens, designs sphériques et formes modulaires. Monographs of L’Enseignement Mathématique, vol. 37, pp. 268–272. Enseignement Mathématique, Geneva (2001)

  12. Erdahl, R.M.: Zonotopes, dicings, and Voronoi’s conjecture on parallelohedra. Eur. J. Comb. 20(6), 527–549 (1999)

    Article  MathSciNet  Google Scholar 

  13. Erdahl, R.M., Ryshkov, S.S.: On lattice dicing. Eur. J. Comb. 15(5), 459–481 (1994)

    Article  MathSciNet  Google Scholar 

  14. Gruber, P.M.: Convex and Discrete Geometry. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 336. Springer, Berlin (2007)

    Google Scholar 

  15. Hanrot, G., Pujol, X., Stehlé, D.: Algorithms for the shortest and closest lattice vector problems. In: Coding and Cryptology. Lecture Notes in Computer Science, vol. 6639, pp. 159–190. Springer, Heidelberg (2011). Corrected version at http://perso.ens-lyon.fr/damien.stehle/downloads/SVPCVP.pdf

  16. Hunkenschröder, C., Reuland, G., Schymura, M.: On compact representations of Voronoi cells of lattices. In: Proceedings of 20th Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 11480, pp. 261–274. Springer, Cham (2019)

  17. Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)

    Article  MathSciNet  Google Scholar 

  18. Kuperberg, G.: From the Mahler conjecture to Gauss linking integrals. Geom. Funct. Anal. 18(3), 870–892 (2008)

    Article  MathSciNet  Google Scholar 

  19. Martinet, J.: Perfect Lattices in Euclidean Spaces. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 327. Springer, Berlin (2003)

    Book  Google Scholar 

  20. McKilliam, R.G., Grant, A., Clarkson, I.V.L.: Finding a closest point in a lattice of Voronoi’s first kind. SIAM J. Discrete Math. 28(3), 1405–1422 (2014)

    Article  MathSciNet  Google Scholar 

  21. Micciancio, D.: The hardness of the closest vector problem with preprocessing. IEEE Trans. Inf. Theory 47(3), 1212–1215 (2001)

    Article  MathSciNet  Google Scholar 

  22. Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM J. Comput. 42(3), 1364–1391 (2013)

    Article  MathSciNet  Google Scholar 

  23. Milnor, J., Husemoller, D.: Symmetric Bilinear Forms. Springer, New York (1973)

    Book  Google Scholar 

  24. Reuland, G.: A Compact Representation of the Voronoi Cell. École Polytechnique Fédérale de Lausanne (January 2018). Master Thesis

  25. Seysen, M.: A measure for the non-orthogonality of a lattice basis. Combin. Probab. Comput. 8(3), 281–291 (1999)

    Article  MathSciNet  Google Scholar 

  26. Vallentin, F.: Sphere coverings, lattices, and tilings (in low dimensions). Ph.D. Thesis, Technical University Munich, Germany (2003)

  27. Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs. J. Reine Angew. Math. 134, 198–287 (1908)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank Daniel Dadush and Frank Vallentin for helpful remarks and suggestions. In particular, Daniel Dadush pointed us to the arguments in Theorem 1 that improved our earlier estimate of order \(\mathcal {O}(n^2 \log {n})\). We are grateful to the referees for their valuable suggestions, questions, and comments.

Author information

Authors and Affiliations

  1. École Polytechnique Fédérale de Lausanne, 1015, Lausanne, Switzerland

    Christoph Hunkenschröder, Gina Reuland & Matthias Schymura

Authors
  1. Christoph Hunkenschröder
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gina Reuland
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matthias Schymura
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matthias Schymura.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was supported by the Swiss National Science Foundation (SNSF) within the project Convexity, geometry of numbers, and the complexity of integer programming (No. 163071). The paper grew out of the master thesis of the second author [24]; an extended abstract of this work appeared as [16].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hunkenschröder, C., Reuland, G. & Schymura, M. On compact representations of Voronoi cells of lattices. Math. Program. 183, 337–358 (2020). https://doi.org/10.1007/s10107-019-01463-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-019-01463-3

Keywords

Mathematics Subject Classification

Search

Navigation