A reverse Minkowski theorem

A reverse Minkowski theorem (via Zoom)

Abstract: Minkowski's celebrated first theorem is one of the foundational results in the study of the geometry of numbers, and it has innumerable applications from basic number theory to convex geometry to cryptography. It tells us that a lattice (i.e., a linear transformation of Z^n) that is globally dense (i.e., has low determinant) must be locally dense (i.e., must have many short vectors). We will show a proof of a nearly tight converse to Minkowski's theorem, originally conjectured by Daniel Dadush---a lattice with many short points must have a sublattice with small determinant. This "reverse Minkowski theorem" has numerous applications in, e.g., complexity theory, additive combinatorics, cryptography, the study of Brownian motion on flat tori, algorithms for lattice problems, etc.

Based on joint work with Oded Regev.

Bio: I am an assistant professor in Cornell's computer science department. My research to date has focused on the study of lattices and using the tools of theoretical computer science to answer fundamental questions about the security of widely deployed real-world cryptography, particularly post-quantum lattice-based cryptography. I am also interested more broadly in theoretical computer science, cryptography, and geometry.

I received my PhD from NYU, advised by Professors Oded Regev and Yevgeniy Dodis. Before coming to Cornell, I was a fellow at the Simons Institute in Berkeley, as part of the program Lattices: Algorithms, Complexity, and Cryptography, a postdoctoral researcher at MIT's computer science department, supervised by Vinod Vaikunthanathan, and a postdoc at Princeton’s computer science department and visiting researcher at the Institute for Advanced Study’s math department---both as part of the Simons Collaboration on Algorithms and Geometry.