Calvin Lab Auditorium
Minkowski's celebrated theorem is one of the foundational results in the study of lattice geometry. It gives us a a tight lower bound on the number of points in a ball of a certain radius that depends only on the determinant of the lattice. (One can think of the determinant as the limit of the density of lattice points inside large balls. So, Minkowski's theorem gives a tight lower bound on a lattice's ?local density? based on its ?global density.?) We will show a proof of a nearly tight converse to Minkowski's theorem, originally conjectured by Dadush---an upper bound on the number of lattice points in a ball that depends only on the determinants of sublattices. This "reverse Minkowski theorem" has numerous applications, from complexity theory, to the geometry of numbers, to the behavior of Brownian motion on flat tori. We will describe recent algorithmic applications. Based on joint work with Oded Regev.