- Series
- ACO Seminar
- Time
- Monday, March 31, 2014 - 4:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Daniel Dadush – New York University
- Organizer
- Robin Thomas

The closest vector problem (CVP) on lattices (i.e. given an n
dimensional lattice L with basis B and target point t, find a closest
lattice point in L to t) is fundamental NP-hard problem with applications
in coding, cryptography & optimization. In this talk, we will consider the
preprocessing version of CVP (CVPP), an important variant of CVP, where we
allow arbitrary time to preprocess the lattice before answering CVP queries.
In breakthrough work, Micciancio & Voulgaris (STOC 2010) gave the first
single exponential time algorithm for CVP under the l_2 norm based on
Voronoi cell computations. More precisely, after a preprocessing step on L
requiring tilde{O}(2^{2n}) time, during which they compute the Voronoi cell
of L (the set of points closer to the origin than to any other point in L),
they show that additional CVP queries on L (i.e. CVPP) can be solved in
tilde{O}(2^{2n}) time.
For our main result, we show that given the Voronoi cell V of L as
preprocessing, CVP on any target t can be solved in expected tilde{O}(2^n)
time. As our main technical contribution, we give a new randomized
procedure that starting from any close enough lattice point to the target
t, follows a path in the Voronoi graph of L (i.e. x,y in L are adjacent if
x+V and y+V share a facet) to the closest lattice vector to t of expected
polynomial size. In contrast, the path used by MV algorithm is only known
to have length bounded by tilde{O}(2^n). Furthermore, for points x,y in L,
we show that the distance between x and y in the Voronoi graph is within a
factor n of ||x-y||_V (norm induced by the Voronoi cell), which is best
possible. For our analysis, we rely on tools from high dimensional convex
geometry. No background in convex geometry or lattices will be assumed.
Time permitting, I will describe related results & open questions about
paths on more general lattice Cayley graphs.
Joint work with Nicolas Bonifas (Ecole Polytechnique).