On compact representations of Voronoi cells of lattices (Q5918916): Difference between revisions

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.