For best experience please turn on javascript and use a modern browser!

Date 31 October 2018 16:00 - 16:45 Science Park 107

### 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.

Science Park 107

Room Location: KdVI meeting room, Science Park 107, room F3.20

Science Park 107
1098 XG Amsterdam