Voronoi cells of lattices with respect to arbitrary norms

DOI10.1137/17M1132045zbMATH Open1429.11117arXiv1512.00720OpenAlexW2963445665MaRDI QIDQ3174772FDOQ3174772

Authors: Johannes Blömer, Kathlén Kohn 

Publication date: 18 July 2018

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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 $el{l}_3$-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 $el{l}_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.

Full work available at URL: https://arxiv.org/abs/1512.00720

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

zbMATH Keywords

latticesVoronoi cellsnormsVoronoi-relevant vectors

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Cites Work

• Convex Analysis
• Title not available (Why is that?)
• Convex Bodies The Brunn-MinkowskiTheory
• The geometry of Minkowski spaces -- a survey. II.
• Title not available (Why is that?)
• Voronoi polytopes for polyhedral norms on lattices
• On bisectors in Minkowski normed spaces
• 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
• Title not available (Why is that?)
• Closest point search in lattices
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Complexity and algorithms for computing Voronoi cells of lattices
• Sampling methods for shortest vectors, closest vectors and successive minima
• Untersuchungen über Wabenzellen bei allgemeiner Minkowskischer Metrik
• Title not available (Why is that?)
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• Title not available (Why is that?)
• Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Cited In (7)

• On the Voronoi Regions of Certain Lattices
• Title not available (Why is that?)
• 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)