On compact representations of Voronoi cells of lattices

DOI10.1007/s10107-019-01463-3zbMath1451.11061arXiv1811.08532OpenAlexW2949230886WikidataQ126411774 ScholiaQ126411774MaRDI QIDQ5918916

Gina Reuland, Christoph Hunkenschröder, Matthias Schymura

Publication date: 28 August 2020

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

latticeszonotopesclosest vector problemVoronoi cellsClosest Vector Problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10) Lattices and convex bodies (number-theoretic aspects) (11H06)

Related Items

Covering convex bodies and the closest vector problem ⋮ Lifts for Voronoi cells of lattices ⋮ The irreducible vectors of a lattice: some theory and applications ⋮ A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices ⋮ On compact representations of Voronoi cells of lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the sum of a parallelotope and a zonotope
• From the Mahler conjecture to Gauss linking integrals
• Zonotopes, dicings, and Voronoi's conjecture on parallelohedra
• On lattice dicing
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
• Hermitian vector bundles and extension groups on arithmetic schemes. I: Geometry of numbers
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• Finding a Closest Point in a Lattice of Voronoi's First Kind
• Algorithms for the Shortest and Closest Lattice Vector Problems
• Minkowski's Convex Body Theorem and Integer Programming
• Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices
• A Measure for the Non-Orthogonality of a Lattice Basis
• The hardness of the closest vector problem with preprocessing
• A sieve algorithm for the shortest lattice vector problem
• Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
• Convex and Discrete Geometry
• Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing
• On compact representations of Voronoi cells of lattices