loading...
Hardness of Approximating the Closest Vector Problem with Pre-Processing
Pittsburgh, Pennsylvania, USA October 23-October 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.4046th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Mikhail Alekhnovich, Mikhail Alekhnovich
Subhash A. Khot, Subhash A. Khot
Nisheeth K. Vishnoi, Nisheeth K. Vishnoi

We show that, unless NP\subseteqDTIME(2^{poly\log (n)}), the closest vector problem with pre-processing, for \ell \rho norm for any p \ge 1, is hard to approximate within a factor of (\log n)^{1/p - \ell } for any \varepsilon > 0. This improves the previous best factor of 3^{1/p} - \varepsilon 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 - \varepsilon } for any \varepsilon > 0.

Citation:
Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler, Nisheeth K. Vishnoi, "Hardness of Approximating the Closest Vector Problem with Pre-Processing," focs, pp.216-225, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.