SCIENCE@home

Lifts for Voronoi Cells of Lattices

Matthias Schymura,Ina Seidel,Stefan Weltge

Published 2021 in Discrete & Computational Geometry

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-45 of 45 references · Page 1 of 1

CITED BY