**Lecture Title: **On Approximating the Covering Radius and Finding Dense Lattice Subspaces

**Presented By: **Daniel Dadush, CWI Amsterdam

**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 theimportant open problem of whether there exists a single exponential timealgorithm 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 explain geometric parameters of the lattice. Inthis 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 showthat 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.

For additional information, please contact Ingrid Varga vargai@cs.toronto.edu.