Hardness of approximating the closest vector problem with pre-processing

We show that, unless NP⊆DTIME(2 poly log(n)), the closest vector problem with pre-processing, for ℓp norm for any p ≥ 1, is hard to approximate within a factor of (log n) 1/p−ɛ for any ɛ> 0. This improves the previous best factor of 3 1/p − ɛ due to Regev [19]. Our results also imply that under the same complexity assumption, the nearest codeword problem with pre-processing is hard to approximate within a factor of (log n) 1−ɛ for any ɛ> 0. 1