Abstract
We show that the problem of approximating the covering radius of a lattice, i.e. approximating the largest distance of any point in space from the lattice, up to a constant factor is in coNP assuming the slicing conjecture for Voronoi cells of so-called stable lattices. This improves on the approximation factor of O(sqrt{log n} x stable voronoi slicing) (or O(log^{3/2} n) unconditionally) achieved by Regev & Stephens-Davidowitz (STOC 17), based on their resolution of the reverse Minkowski conjecture.
Our characterization relies upon the canonical filtration of a lattice, as does that of Regev & Stephens-Davidowitz, i.e. canonical way to decompose a lattice along dense lattice subspaces, combined with a convex relaxation of the covering radius due to Dadush & Regev (FOCS 2016). From the algorithmic perspective, we show how to compute an O(log n) approximate version of the canonical filtration in 2^{n+o(n)} time, using discrete Gaussian sampling and a new form of basis reduction that we call filtration reduction.
As a companion contribution, we show that the slicing constant of any Voronoi cell is bounded by O(log^{3/2} n), which complements the O(log n) achieved by Regev & Stephens-Davidowitz for Voronoi cell of stable lattices.