@misc{SchymuraSeidelWeltge, author = {Schymura, Matthias and Seidel, Ina and Weltge, Stefan}, title = {Lifts for Voronoi cells of lattices}, series = {Discrete \& Computational Geometry}, volume = {70}, journal = {Discrete \& Computational Geometry}, number = {3}, publisher = {Springer US}, issn = {0179-5376}, doi = {10.1007/s00454-023-00522-z}, pages = {845 -- 865}, 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/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.}, language = {en} }