TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Kathlén Kohn

Inhalt des Dokuments

zur Navigation

Ehemalige Mitarbeiter

Prof. Dr. Kathlén Kohn


Institutionen för Matematik
Lindstedtsvägen 25
10044 Stockholm

Persönliche Homepage:

Publikationen in der Arbeitsgruppe

Voronoi cells of lattices with respect to arbitrary norms
Zitatschlüssel BK-Voronoi-Cells-Of-Lattices-With-Respect-To-Arbitrary-Norms
Autor Johannes Blömer and Kathlén Kohn
Seiten 314–338
Jahr 2018
DOI 10.1137/17M1132045
Journal SIAM J. Appl. Algebra Geom.
Jahrgang 2
Nummer 2
Monat 06
Zusammenfassung We study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms. On the positive side, we show for strictly convex and smooth norms that 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 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 Voronoi cells are combinatorially much more complicated for arbitrary strictly convex and smooth norms 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 $\ell_3$-norm is unbounded. Our result indicates that the single exponential time algorithm of Micciancio and Voulgaris for solving the shortest vector problem (SVP) and the closest vector problem (CVP) in the Euclidean norm cannot be extended to achieve deterministic single exponential time algorithms for lattice problems with respect to arbitrary $\ell_p$-norms. In fact, the algorithm of Micciancio and Voulgaris and its run time analysis crucially depend on the fact that, for the Euclidean norm, the number of Voronoi-relevant vectors is single exponential in the lattice dimension.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe