**Authors:** Uriel Feige and Daniele Micciancio

Journal of Computer and System Sciences, 69(1), pp. 45-6, 2004. (Preliminary version in CCC 2002.)

**Abstract:** We prove that the closest vector problem with
preprocessing (CVPP) is NP-hard to approximate within any factor less than
sqrt{5/3}. More specifically, we show that there exists a reduction from an
NP-hard problem to the approximate closest vector problem such that the
lattice depends only on the size of the original problem, and the specific
instance is encoded solely in the target vector. It follows that there are
lattices for which the closest vector problem cannot be approximated within
factors gamma < sqrt{5/3} in polynomial time, no matter how the lattice is
represented, unless NP is equal to P (or NP is contained in P/poly, in case
of nonuniform sequences of lattices). The result easily extends to any L_p
norm, for p >= 1, showing that CVPP in the L_p norm is hard to approximate
within any factor gamma < {5/3}^{1/p}. As an intermediate step, we
establish analogous results for the nearest codeword problem with
preprocessing (NCPP), proving that for any finite field GF(q), NCPP over
GF(q) is NP-hard to approximate within any factor less than 5/3.

**Preliminary version:** U. Feige, D. Micciancio, The
inapproximability of lattice and coding problems with preprocessing, IEEE
Computational Complexity Conference - CCC 2002. May 21-23. Montreal, Canada.
pp. 44-52.