Theory Seminar, February 16, 2:00pm
Warren Weaver Hall, Room 312

Convex Geometry and Lattice Problems: New Connections and Algorithms
 
Daniel Dadush, Georgia Tech

In this talk, I will survey newly discovered relationships and algorithms for some fundamental lattice and convex geometry problems: the shortest / closest vector problem (SVP & CVP), integer programming (IP), and volume estimation for convex bodies. Here we obtain algorithmic improvements from the perspectives of derandomization (SVP, CVP and volume estimation) and increased efficiency (IP). I will describe major technical tools behind our improvements, including the use of the M-ellipsoid from convex geometry - an ellipsoid with good covering properties w.r.t. a convex body - and extremal lattices from the geometry of numbers - lattices for which the packing and covering properties w.r.t. a convex body are nearly identical.