Georgia Institute of Technology College of Sciences

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).