Voronoi cells of lattices with respect to arbitrary norms
From MaRDI portal
Publication:3174772
Abstract: 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 -norm is unbounded. Our result indicates, that the break through single exponential time algorithm of Micciancio and Voulgaris for solving the shortest and closest vector problem in the Euclidean norm cannot be extended to achieve deterministic single exponential time algorithms for lattice problems with respect to arbitrary -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.
Recommendations
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- Voronoi polytopes for polyhedral norms on lattices
- Complexity and algorithms for computing Voronoi cells of lattices
Cites work
- scientific article; zbMATH DE number 3842691 (Why is no real title available?)
- scientific article; zbMATH DE number 45409 (Why is no real title available?)
- scientific article; zbMATH DE number 1224949 (Why is no real title available?)
- scientific article; zbMATH DE number 1520171 (Why is no real title available?)
- scientific article; zbMATH DE number 6607548 (Why is no real title available?)
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- Approximating CVP to within almost-polynomial factors is NP-hard
- Closest point search in lattices
- Complexity and algorithms for computing Voronoi cells of lattices
- Convex Analysis
- Convex Bodies The Brunn-MinkowskiTheory
- Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- On bisectors in Minkowski normed spaces
- Sampling methods for shortest vectors, closest vectors and successive minima
- Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
- Tensor-based hardness of the shortest vector problem to within almost polynomial factors
- The geometry of Minkowski spaces -- a survey. II.
- Untersuchungen über Wabenzellen bei allgemeiner Minkowskischer Metrik
- Voronoi polytopes for polyhedral norms on lattices
Cited in
(7)- scientific article; zbMATH DE number 17391 (Why is no real title available?)
- On the Voronoi Regions of Certain Lattices
- Voronoi polytopes for polyhedral norms on lattices
- Lifts for Voronoi cells of lattices
- Voronoi-like partition of lattice in cellular automata
- Asymmetric tropical distances and power diagrams
- Théorie de Voronoï géométrique. Propriétés de finitude pour les familles de réseaux et analogues
This page was built for publication: Voronoi cells of lattices with respect to arbitrary norms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174772)
