Lifts for Voronoi Cells of Lattices

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/logd) 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(dlog d) facets, respectively. We obtain similar results for spectrahedral lifts.