  We give a deterministic algorithm for solving the (1+eps)-approximate Closest
Vector Problem (CVP) on any n dimensional lattice and any 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)
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 l_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) for the purpose of proving hardness for Shortest Vector
Problem (SVP) under l_p norms.
