---
res:
bibo_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.
bibo_authorlist:
- foaf_Person:
foaf_givenName: Johannes
foaf_name: Blömer, Johannes
foaf_surname: Blömer
foaf_workInfoHomepage: http://www.librecat.org/personId=23
- foaf_Person:
foaf_givenName: Kathlén
foaf_name: Kohn, Kathlén
foaf_surname: Kohn
dct_date: 2015^xs_gYear
dct_publisher: Universität Paderborn@
dct_title: Voronoi Cells of Lattices with Respect to Arbitrary Norms@
...