### DIMACS Theoretical Computer Science Seminar

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

Speaker: **M. Alekhnovitch**

Date: April 19, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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}.$