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})}$$ 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 $${{\mathcal {O}}}(d)$$ O ( d ) and $${{\mathcal {O}}}(d \log d)$$ O ( d log d ) facets, respectively. We obtain similar results for spectrahedral lifts.

Abstract We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of d/2 in dimension d, achieved by the “standard terminal simplices” and direct sums of them. We prove this conjecture up to dimension three and show it to be equivalent to the conjecture of González-Merino and Schymura (Discrete Comput. Geom. 58(3), 663–685 (2017)) that the d-th covering minimum of the standard terminal n-simplex equals d/2, for every $$n\ge d$$ n ≥ d . We also show that these two conjectures would follow from a discrete analog for lattice simplices of Hadwiger’s formula bounding the covering radius of a convex body in terms of the ratio of surface area versus volume. To this end, we introduce a new notion of discrete surface area of non-hollow simplices. We prove our discrete analog in dimension two and give strong evidence for its validity in arbitrary dimension.