Voronoi Cells of Lattices with Respect to Arbitrary Norms

J. Blömer, K. Kohn, Voronoi Cells of Lattices with Respect to Arbitrary Norms, Universität Paderborn, 2015.

Download
Restricted 233-1512.00720v1.pdf 1.23 MB
Report
Author
Blömer, JohannesLibreCat; Kohn, Kathlén
Abstract
Motivated by the deterministic single exponential time algorithm of Micciancio and Voulgaris for solving the shortest and closest vector problem for the Euclidean norm, we study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms.On the positive side, we show that for strictly convex and smooth norms the geometry of Voronoi cells of lattices in any dimension is similar to the Euclidean case, i.e., the Voronoi cells are defined by the so-called Voronoi-relevant vectors and the facets of a Voronoi cell are in one-to-one correspondence with these vectors. On the negative side, we show that combinatorially Voronoi cells for arbitrary strictly convex and smooth norms are much more complicated than in the Euclidean case.In particular, we construct a family of three-dimensional lattices whose number of Voronoi-relevant vectors with respect to the l_3-norm is unbounded.Since the algorithm of Micciancio and Voulgaris and its run time analysis crucially dependonthefactthatfortheEuclidean normthenumber of Voronoi-relevant vectors is single exponential in the lattice dimension, this indicates that the techniques of Micciancio and Voulgaris cannot be extended to achieve deterministic single exponential time algorithms for lattice problems with respect to arbitrary l_p-norms.
Publishing Year
LibreCat-ID
233

Cite this

Blömer J, Kohn K. Voronoi Cells of Lattices with Respect to Arbitrary Norms. Universität Paderborn; 2015.
Blömer, J., & Kohn, K. (2015). Voronoi Cells of Lattices with Respect to Arbitrary Norms. Universität Paderborn.
@book{Blömer_Kohn_2015, title={Voronoi Cells of Lattices with Respect to Arbitrary Norms}, publisher={Universität Paderborn}, author={Blömer, Johannes and Kohn, Kathlén}, year={2015} }
Blömer, Johannes, and Kathlén Kohn. Voronoi Cells of Lattices with Respect to Arbitrary Norms. Universität Paderborn, 2015.
J. Blömer and K. Kohn, Voronoi Cells of Lattices with Respect to Arbitrary Norms. Universität Paderborn, 2015.
Blömer, Johannes, and Kathlén Kohn. Voronoi Cells of Lattices with Respect to Arbitrary Norms. Universität Paderborn, 2015.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
233-1512.00720v1.pdf 1.23 MB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T10:30:18Z


Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar