On compact representations of Voronoi cells of lattices (Q5918916)

An \(n\) dimensional lattice is the integral linear span of \(n\) linearly independent vectors in \(n\) dimensional Euclidean space. The closest vector problem seeks a lattice vector that minimizes the Euclidean distance to a given lattice point. The authors study the open problem of the existence of an algorithm for the closest vector problem on lattices that requires only polynomial space. They define a basis of a lattice to be \(c\)-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using only coefficients whose magnitude are bounded by \(c.\) In this situation, they give a polynomial space algorithm for the closest vector problem that depends on \(c\). With respect to this result they prove three results. The first is that there always exist \(c\)-compact bases for an \(n\) dimensional lattice, where \(c\) is bounded by \(n^2\). The second is that there exist lattices not admitting a \(c\)-compact basis with \(c\) growing sublinearly with the dimension. The third is that every lattice with a zonotopal Voronoi cell has a \(1\)-compact basis.