Return to Colloquia & Seminar listing
Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings
Algebra & Discrete Mathematics| Speaker: | Daniel Dadush, Georgia Tech |
| Location: | 2112 MSB |
| Start time: | Fri, Oct 28 2011, 2:10PM |
Description
We give a novel algorithm for enumerating lattice points in any convex
body, and give applications to several classic lattice problems,
including the Shortest and Closest Vector Problems (SVP and CVP,
respectively) and Integer Programming (IP). Our enumeration technique
relies on a classical concept from asymptotic convex geometry known as
the M-ellipsoid, and uses as a crucial subroutine the recent
algorithm of Micciancio and Voulgaris (STOC 2010) for lattice problems
in the l_2 norm. As a main technical contribution, which may
be of independent interest, we build on the techniques of Klartag
(Geometric and Functional Analysis, 2006) to give an expected
2^{O(n)}-time algorithm for computing an M-ellipsoid for any
n-dimensional convex body.