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