direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Wissenschaftliche Mitarbeiter

Kathlén Kohn

Lupe

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 319
Institut für Mathematik

Persönliche Homepage:
page.math.tu-berlin.de/~kohn/

Kontakt

Sekretariat
MA 6-2
Antje Schulz, Raum MA 625
+49 (0)30 314 - 28643

eMail
kohnok@outermath.tu-berlin.de

Telefon
+49 (0)30 314 - 29280
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde

Während der Vorlesungszeit: Montag 1500-1700
Während der vorlesungsfreien Zeit: Nach Vereinbarung.

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
Jahr 2015
Monat 12
Zusammenfassung 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 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 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 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. Since 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, 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 $\ell_p$-norms.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe