Hardness of Approximating the Closest Vector Problem with Pre-Processing
Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi · 2005
We show that, unless NP/spl sube/DTIME(2/sup poly log(n)/) the closest vector problem with pre-processing, for /spl lscr//sub p/ norm for any p /spl ges/ 1, is hard to approximate within a factor of (log n)/sup 1/p - /spl epsi//' /P for any /spl epsi/ > 0. This improves the previous best factor of 3/sup 1/p/ - /spl epsi/ due to Regev (2004). 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)/sup 1 - /spl epsi//' for any /spl epsi/ > 0.