BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Monday Seminars : Recent Progress on Lattice Problems\, Volume 
 Estimation\, and Integer Programming
DTSTART:20120319T161500
DTSTAMP:20260407T014029Z
UID:93582c559ed1ade5e4c1dcb44712d8879361de88c3f3a4fb6c8a430d
CATEGORIES:Conferences - Seminars
DESCRIPTION:Daniel Dadush\, Georgia Institute of Technology - IC Faculty c
 andidate\nAbstract\nIt has been known since Minkowski that there is a deep
  and fascinating interplay between convexity and discrete lattice structur
 es. In this talk\, I will overview new\nconnections between algorithmic co
 nvex geometry and the study of lattice problems\, and show how they enable
  complexity improvements for problems in both areas.\n\nThe Shortest (SVP)
  and Closest Vector (CVP) Problems are classic NP-Hard lattice problems wi
 th applications to Cryptography\, Communication Theory\, Integer\nProgramm
 ing\, and more. In the first part of the talk\, I will explain how to use 
 M-ellipsoid coverings from convex geometry and a new lattice sparsificatio
 n technique\nto give the first deterministic single exponential time algor
 ithms for SVP and approximate CVP under general norms. These yield the fir
 st deterministic counterparts to\nthe extant Monte Carlo algorithms for th
 ese problems\, which use the randomized sieving technique of Ajtai\, Kumar
  and Sivakumar (STOC `00).\n\nEstimating the volume a convex body is an ol
 d problem whose study has precipitated many important discoveries in algor
 ithmic convex geometry. All current\npolynomial time algorithms for volume
  estimation are based on monte carlo markov chain techniques\, and little 
 progress has been made in finding deterministic\ncounterparts. In the seco
 nd part of the talk\, I will give a reduction from volume estimation to M-
 ellipsoid computation and lattice point counting. This yields a\ndetermini
 stic single exponential algorithm that is essentially optimal when given o
 nly oracle access to a convex body. I will also describe how these techniq
 ues\ncan be adapted to compute polyhedral approximations and centers of sy
 mmetry for general convex bodies.\n\nThe Integer Programming Problem (IP)\
 , i.e. optimization over the integer points in a convex set\, is a fundame
 ntal algorithmic problem in Computer Science and\nOperations Research. In 
 the last part of talk\, I will show how to combine all the previous algori
 thms to give the first O(n)^n time algorithm to minimize a convex\nfunctio
 n over the integer points in an n dimensional convex body. This yields the
  fastest known algorithm for IP and improves on the seminal works of Lenst
 ra and\nKannan.\n\nBiography\nDaniel Dadush is currently a PhD student at 
 Georgia Tech under professor Santosh Vempala. Previously\, he completed a 
 BS in Mathematics at Brown University. His research interests include algo
 rithmic convex geometry\, lattice problems and the geometry of numbers\, a
 s well computational complexity writ large.
LOCATION:INM 202
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR