IC Monday Seminars : Recent Progress on Lattice Problems, Volume Estimation, and Integer Programming
Event details
| Date | 19.03.2012 |
| Hour | 16:15 |
| Speaker | Daniel Dadush, Georgia Institute of Technology - IC Faculty candidate |
| Location |
INM 202
|
| Category | Conferences - Seminars |
Abstract
It has been known since Minkowski that there is a deep and fascinating interplay between convexity and discrete lattice structures. In this talk, I will overview new
connections between algorithmic convex geometry and the study of lattice problems, and show how they enable complexity improvements for problems in both areas.
The Shortest (SVP) and Closest Vector (CVP) Problems are classic NP-Hard lattice problems with applications to Cryptography, Communication Theory, Integer
Programming, 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 sparsification technique
to give the first deterministic single exponential time algorithms for SVP and approximate CVP under general norms. These yield the first deterministic counterparts to
the extant Monte Carlo algorithms for these problems, which use the randomized sieving technique of Ajtai, Kumar and Sivakumar (STOC `00).
Estimating the volume a convex body is an old problem whose study has precipitated many important discoveries in algorithmic convex geometry. All current
polynomial time algorithms for volume estimation are based on monte carlo markov chain techniques, and little progress has been made in finding deterministic
counterparts. In the second part of the talk, I will give a reduction from volume estimation to M-ellipsoid computation and lattice point counting. This yields a
deterministic single exponential algorithm that is essentially optimal when given only oracle access to a convex body. I will also describe how these techniques
can be adapted to compute polyhedral approximations and centers of symmetry for general convex bodies.
The Integer Programming Problem (IP), i.e. optimization over the integer points in a convex set, is a fundamental algorithmic problem in Computer Science and
Operations Research. In the last part of talk, I will show how to combine all the previous algorithms to give the first O(n)^n time algorithm to minimize a convex
function 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 Lenstra and
Kannan.
Biography
Daniel 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 algorithmic convex geometry, lattice problems and the geometry of numbers, as well computational complexity writ large.
It has been known since Minkowski that there is a deep and fascinating interplay between convexity and discrete lattice structures. In this talk, I will overview new
connections between algorithmic convex geometry and the study of lattice problems, and show how they enable complexity improvements for problems in both areas.
The Shortest (SVP) and Closest Vector (CVP) Problems are classic NP-Hard lattice problems with applications to Cryptography, Communication Theory, Integer
Programming, 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 sparsification technique
to give the first deterministic single exponential time algorithms for SVP and approximate CVP under general norms. These yield the first deterministic counterparts to
the extant Monte Carlo algorithms for these problems, which use the randomized sieving technique of Ajtai, Kumar and Sivakumar (STOC `00).
Estimating the volume a convex body is an old problem whose study has precipitated many important discoveries in algorithmic convex geometry. All current
polynomial time algorithms for volume estimation are based on monte carlo markov chain techniques, and little progress has been made in finding deterministic
counterparts. In the second part of the talk, I will give a reduction from volume estimation to M-ellipsoid computation and lattice point counting. This yields a
deterministic single exponential algorithm that is essentially optimal when given only oracle access to a convex body. I will also describe how these techniques
can be adapted to compute polyhedral approximations and centers of symmetry for general convex bodies.
The Integer Programming Problem (IP), i.e. optimization over the integer points in a convex set, is a fundamental algorithmic problem in Computer Science and
Operations Research. In the last part of talk, I will show how to combine all the previous algorithms to give the first O(n)^n time algorithm to minimize a convex
function 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 Lenstra and
Kannan.
Biography
Daniel 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 algorithmic convex geometry, lattice problems and the geometry of numbers, as well computational complexity writ large.
Links
Practical information
- Informed public
- Free
- This event is internal
Contact
- Christine Moscioni