loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
Hardness of Approximating the Closest Vector Problem with Pre-Processing
Pittsburgh, Pennsylvania, USA
October 23-October 25
ISBN: 0-7695-2468-0
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.