Theory of Computing
-------------------
Title     : Lattice Sparsification and the Approximate Closest Vector Problem
Authors   : Daniel Dadush and Gabor Kun
Volume    : 12
Number    : 2
Pages     : 1-34
URL       : https://theoryofcomputing.org/articles/v012a002

Abstract
--------

We give a deterministic algorithm for solving the
$(1+\eps)$-approximate Closest Vector Problem (CVP) on any
$n$-dimensional lattice and in any near-symmetric norm in
$2^{O(n)}(1+1/\eps)^n$ time and $2^n\poly(n)$ space. Our algorithm
builds on the lattice point enumeration techniques of Micciancio and
Voulgaris (STOC 2010, SICOMP 2013) and Dadush, Peikert and Vempala
(FOCS 2011), and gives an elegant, deterministic alternative to the
"AKS Sieve"-based algorithms for $(1+\eps)$-CVP (Ajtai, Kumar, and
Sivakumar; STOC 2001 and CCC 2002). Furthermore, assuming the
existence of a $\poly(n)$-space and $2^{O(n)}$-time algorithm for
exact CVP in the $\ell_2$ norm, the space complexity of our algorithm
can be reduced to polynomial.

Our main technical contribution is a method for "sparsifying" any
input lattice while approximately maintaining its metric structure. To
this end, we employ the idea of random sublattice restrictions, which
was first employed by Khot (FOCS 2003, J. Comp. Syst. Sci. 2006) for
the purpose of proving hardness for the Shortest Vector Problem (SVP)
under $\ell_p$ norms.

A preliminary version of this paper appeared in the Proc. 24th Annual 
ACM-SIAM Symp. on Discrete Algorithms (SODA'13)
(http://dx.doi.org/10.1137/1.9781611973105.78).