Improving on the Voronoi cell based techniques of [28, 24], we give a Las Vegas Õ (2n) expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the Õ(4n) deterministic runtime of the Micciancio Voulgaris algorithm [24] (henceforth MV) for CVPP1 at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that, given the Voronoi relevant vectors of a lattice – the lattice vectors inducing facets of the Voronoi cell – as preprocessing, and any “close enough” lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the Õ(2n) path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest.

We derive a new upper bound on the diameter of the graph of a polyhedron P = {x ∈ Rn : Ax ≤ b}, where A ∈ Zm×n. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O(Δ2 n4 log nΔ). If P is bounded, then we show that the diameter of P is at most O(Δ2 n3.5 log nΔ).