A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices

DOI10.1137/20M1382258MaRDI QIDQ5163506

Britta Peis, Robert Scheidweiler, Frank Vallentin, S. Thomas McCormick

Publication date: 4 November 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

latticeVoronoi cellzonotopeclosest vector problemtotally unimodular matrixminimum mean cycle canceling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Related Items (1)

Lifts for Voronoi cells of lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The LLL algorithm. Survey and applications
• Decomposition of regular matroids
• Die Jaboci-Abbildung über dem Raum der Mumfordkurven
• Zonotopes, dicings, and Voronoi's conjecture on parallelohedra
• On lattice dicing
• The closest vector problem in tensored root lattices of type A and in their duals
• Approximating CVP to within almost-polynomial factors is NP-hard
• Unimodular modules
• The classification of zonohedra by means of projective diagrams
• 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
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Complexity and algorithms for computing Voronoi cells of lattices
• Finding minimum-cost circulations by canceling negative cycles
• Lattice problems in NP ∩ coNP
• Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices
• Space‐filling zonotopes
• Space tiling zonotopes
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications
• A strongly polynomial algorithm for bimodular integer linear programming
• Lectures on matroids
• Convex Analysis
• Convex separable optimization is not much harder than linear optimization
• On compact representations of Voronoi cells of lattices

This page was built for publication: A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices