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
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.40
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||