Title:

On Approximating the Covering Radius and Finding Dense Lattice Subspaces

Abstract:

Minkowski's first fundamental theorem in its counting form tells us that in a Euclidean lattice of determinant 1, the number of lattice points contained in any origin centered ball is essentially lower bounded by its volume. A natural question is whether this statement can be usefully reversed: namely, if all sublattices of the lattice have determinant at least 1 (i.e. are sparse), can one derive a good upper bound on the number of points in any origin centered ball? In recent breakthrough work, Regev and Stephens-Davidowitz (STOC `17) answered this question in the affirmative, establishing a so-called reverse Minkowski theorem. Following up on this work, our first result is an algorithmic counterpart to the reverse Minkowski theorem, namely we give a natural exponential time algorithm for finding approximately densest sublattices. 

The initial motivation for this theory, as developed by Regev and the author (FOCS `16), was to tackle the dual problem of tightly characterizing the covering radius of a lattice (i.e. farthest distance to the lattice) in terms of only determinantal information. A main application of the reverse Minkowski theorem was to show that such information characterizes the covering radius up to a polylogarithmic factor in dimension, resolving a conjecture of Kannan and Lovasz (Annals of Math `88). For our second result, under the assumption that the integer lattice approximately maximizes the covering radius among all so-called stable lattices, we improve this approximate characterization to be constant factor tight, removing any dependence on dimension.