Open Collections

The Reverse Minkowski Theorem

Banff International Research Station for Mathematical Innovation and Discovery

Informally, Minkowski's first theorem states that lattices that are globally dense (have small determinant) are also locally dense (have lots of points in a small ball around the origin). This fundamental result dates back to 1891 and has a very wide range of applications. Here we prove a reverse form of the Minkowski's theorem, showing that locally dense lattice are also globally dense (in the appropriate sense). We also discuss the many applications of this result. In particular, it resolves a conjecture by Saloff-Coste on the behavior of random walks on flat tori, has implications to the complexity of lattice problems, and also makes progress on conjectures by Kannan and Lovasz, and by Shapira and Weiss that are closely related to a celebrated conjecture by Minkowski. Based on joint works with Daniel Dadush and Noah Stephens-Davidowitz.

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: New York University

2017-03-09

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/60857

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/