Lifts for Voronoi cells of lattices

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^{\Omega (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.

17 pages