On approximating the covering radius and finding dense lattice subspaces
In this work, we give a novel algorithm for computing dense lattice subspaces, a conjecturally tight characterization of the lattice covering radius, and provide a bound on the slicing constant of lattice Voronoi cells. Our work is motivated by the pursuit of faster algorithms for integer programming, for which we give a conditional speedup based on the recent resolution of the ℓ2 Kannan-Lovász conjecture. Through these results, we hope to motivate further study of the interplay between the recently developed reverse Minkowski theory, lattice algorithms and convex geometry.
On the algorithmic side, our main contribution is a 2O(n)-time algorithm for computing a O(Cη(n))-approximate sublattice of minimum normalized determinant on any n-dimensional lattice, where Cη(n) = O(logn) is the reverse Minkowski constant in dimension n. Our method for finding dense lattice subspaces is surprisingly simple: we iteratively descend to a random co-dimension 1 subspace chosen to be the orthogonal space to a discrete Gaussian sample from the dual lattice. Applying this algorithm within a “filtration reduction” scheme, we further show how to compute a O(Cη(n))-approximate canonical filtration of any lattice, which corresponds to a canonical way of decomposing a lattice into dense blocks. As a primary application, we get the first 2O(n)-time algorithm for computing a sparse lattice projection whose “volume radius” provides a lower bound on the lattice covering radius that is tight within a O(log2.5 n)-factor. This provides an efficient algorithmic version of the ℓ2 Kannan-Lovász conjecture, which was recently resolved by Regev and Stephens-Davidowitz (STOC’2017).
On the structural side, we prove a new lower bound on the covering radius which combines volumetric lower bounds across a chain of lattice projections. Assuming Bourgain’s slicing conjecture restricted to Voronoi cells of stable lattices, our lower bound implies (somewhat surprisingly) that the problem of approximating the lattice covering radius to within a constant factor is in coNP. Complementing this result, we show that the slicing constant of any n-dimensional Voronoi cell is bounded by O(CKL,2(n)) = O(log1.5 n), the ℓ2 Kannan-Lovász constant, which complements the O(log n) bound of Regev and Stephens-Davidowitz for stable Voronoi cells.
|Annual ACM SIGACT Symposium on Theory of Computing|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Dadush, D.N. (2019). On approximating the covering radius and finding dense lattice subspaces. In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (pp. 1021–1026). doi:10.1145/3313276.3316397