TY - GEN A1 - Schymura, Matthias A1 - Seidel, Ina A1 - Weltge, Stefan T1 - Lifts for Voronoi cells of lattices T2 - Discrete & Computational Geometry N2 - 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(dlogd)facets, respectively. We obtain similar results for spectrahedral lifts. KW - Lattices KW - Voronoi cells KW - Extended formulations KW - 52B05 KW - 52B12 KW - 90C05 KW - 52C07 KW - Mathematical Sciences Y1 - 2023 U6 - https://doi.org/10.1007/s00454-023-00522-z SN - 0179-5376 SN - 1432-0444 VL - 70 IS - 3 SP - 845 EP - 865 PB - Springer US ER -