On Approximating the Covering Radius and Finding Dense Lattice Subspaces

          @misc{ scivideos_15400,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tba-137},
            author = {},
            keywords = {},
            language = {en},
            title = {On Approximating the Covering Radius and Finding Dense Lattice Subspaces},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15400 see, \url{https://scivideos.org/Simons-Institute/15400}}
          }
          

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. One may wonder if this statement can be 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? Regev and Stephens-Davidowitz (STOC `17) answered this question in the affirmative, establishing a so-called reverse Minkowski theorem. Building on this work, our first main result is an algorithmic counterpart to the reverse Minkowski theorem, where we give a Discrete Gaussian Sampling based exponential time algorithm for finding O(log n)-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 determinants of projected sublattices. In particular, we showed that assuming the reverse Minkowski theorem, the covering radius of a lattice can be determined up to polylogarithmic factors using only such determinantal information, 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. In particular, this conjecture implies that the problem of approximating the covering radius up to O(1)-factors is in coNP.