---
_id: '233'
abstract:
- lang: eng
text: 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.
author:
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
- first_name: Kathlén
full_name: Kohn, Kathlén
last_name: Kohn
citation:
ama: Blömer J, Kohn K. *Voronoi Cells of Lattices with Respect to Arbitrary Norms*.
Universität Paderborn; 2015.
apa: Blömer, J., & Kohn, K. (2015). *Voronoi Cells of Lattices with Respect
to Arbitrary Norms*. Universität Paderborn.
bibtex: '@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} }'
chicago: Blömer, Johannes, and Kathlén Kohn. *Voronoi Cells of Lattices with Respect
to Arbitrary Norms*. Universität Paderborn, 2015.
ieee: J. Blömer and K. Kohn, *Voronoi Cells of Lattices with Respect to Arbitrary
Norms*. Universität Paderborn, 2015.
mla: Blömer, Johannes, and Kathlén Kohn. *Voronoi Cells of Lattices with Respect
to Arbitrary Norms*. Universität Paderborn, 2015.
short: J. Blömer, K. Kohn, Voronoi Cells of Lattices with Respect to Arbitrary Norms,
Universität Paderborn, 2015.
date_created: 2017-10-17T12:41:37Z
date_updated: 2022-01-06T06:55:49Z
ddc:
- '040'
department:
- _id: '64'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T10:30:18Z
date_updated: 2018-03-21T10:30:18Z
file_id: '1501'
file_name: 233-1512.00720v1.pdf
file_size: 1231102
relation: main_file
success: 1
file_date_updated: 2018-03-21T10:30:18Z
has_accepted_license: '1'
main_file_link:
- open_access: '1'
url: http://arxiv.org/pdf/1512.00720v1.pdf
oa: '1'
project:
- _id: '1'
name: SFB 901
- _id: '13'
name: SFB 901 - Subprojekt C1
- _id: '4'
name: SFB 901 - Project Area C
publisher: Universität Paderborn
status: public
title: Voronoi Cells of Lattices with Respect to Arbitrary Norms
type: report
user_id: '25078'
year: '2015'
...