Title: Hardness of Approximating the Closest Vector Problem with 
Pre-Processing

Speaker: M. Alekhnovitch. 

Abstract:

We show that, unless NP$\subseteq${\sf DTIME}$QP
the Closest Vector Problem with Pre-processing, for $\ell_p$ norm 
for any $p \geq 1,$  is hard to approximate within a factor of
$(\log n)^{1/p-\epsilon}.$  This improves the previous best factor
$3^{1/p}$ due to Regev. Our results also imply that for any 
$\epsilon>0,$ under the same complexity assumption, the Nearest Codeword 
Problem with Pre-processing is hard to approximate within a factor of 
$(\log n)^{1-\epsilon}.$
-------------------------------------------------------