Lifts for Voronoi cells of lattices

2021/06/08 by Schymura, Matthias, Seidel, Ina, Weltge, Stefan
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2106.04432

Abstract

Many polytopes arising in polyhedral combinatorics are linear projections of higher-dimensional polytopes with significantly fewer facets. Such lifts may yield compressed representations of polytopes, which are typically used to construct small-size linear programs. Motivated by algorithmic implications for the closest vector problem, we study lifts of Voronoi cells of lattices. We construct an explicit d-dimensional lattice such that every lift of the respective Voronoi cell has 2^{Ω(d / log d)} facets. On the positive side, we show that Voronoi cells of d-dimensional root lattices and their dual lattices have lifts with O(d) and O(d log d) facets, respectively. We obtain similar results for spectrahedral lifts.

Related

• Algebraic Characterization of the Voronoi Cell Structure of the A_n Lattice
• Voronoi Cells of Lattices with Respect to Arbitrary Norms
• Voronoi Polytopes for Polyhedral Norms on Lattices
• On the Structure of Higher Order Voronoi Cells
• Voronoi cells of discrete point sets