Cryptography Seminar

Please note that the list below only shows forthcoming events, which may not include regular events that have not yet been entered for the forthcoming term. Please see the past events page for a list of all seminar series that the department has on offer.

Past events in this series
Tomorrow
15:00
Daniel Dadush
Abstract

Integer programming, the problem of finding an optimal integer solution satisfying linear constraints, is one of the most fundamental problems in discrete optimization. In the first part of this talk, I will discuss the important open problem of whether there exists a single exponential time algorithm for solving a general n variable integer program, where the best current algorithm requires n^{O(n)} time. I will use this to motivate a beautiful conjecture of Kannan & Lovasz (KL) regarding how "flat" convex bodies not containing integer points must be.

The l_2 case of KL was recently resolved in breakthrough work by Regev & Davidowitz `17, who proved a more general "Reverse Minkowski" theorem which gives an effective way of bounding lattice point counts inside any ball around the origin as a function of sublattice determinants. In both cases, they prove the existence of certain "witness" lattice subspaces in a non-constructive way that explains geometric parameters of the lattice. In this work, as my first result, I show how to make these results constructive in 2^{O(n)} time, i.e. which can actually find these witness subspaces, using discrete Gaussian sampling techniques. As a second main result, I show an improved complexity characterization for approximating the covering radius of a lattice, i.e. the farthest distance of any point in space to the lattice. In particular, assuming the slicing conjecture, I show that this problem is in coNP for constant approximation factor, which improves on the corresponding O(log^{3/2} n) approximation factor given by Regev & Davidowitz's proof of the l_2 KL conjecture.

  • Cryptography Seminar
Add to My Calendar