•   When: Monday, March 22, 2021 from 11:00 AM to 12:00 PM
•   Speakers: Huck Bennett, Postdoc, University of Michigan
•   Location: ZOOM
•   Export to iCal

ABSTRACT:
The area of fine-grained complexity works to establish strong runtime lower bounds by giving highly efficient reductions between computational problems. Understanding the fine-grained complexity of computational problems on lattices -- geometric objects that underlie much of modern cryptography -- is especially well-motivated by the need to understand the precise security of real-world, lattice-based cryptosystems. Indeed, the difference in solving a lattice problem in 2^n- versus 2^(n/20)- versus 2^sqrt(n)-time may mean the difference between a cryptosystem being secure, insecure with current parameters, and effectively broken in practice.

In this talk, I will survey recent work on the fine-grained complexity of lattice problems, with a focus on the Closest Vector Problem (CVP) and one of its variants, the Bounded Distance Decoding Problem (BDD). I will also describe connections between the geometry of lattices and proving lower bounds.

 BIO:

 Huck Bennett is a postdoc at the University of Michigan. Previously, he was a postdoc at Northwestern University. He received his Ph.D. in computer science from the Courant Institute of Mathematical Sciences at New York University in 2017 advised by Daniel Dadush and Chee Yap. His research area is theoretical computer science, with an emphasis on geometric algorithms and the complexity of lattice problems.