Hardness of approximating the closest vector problem with pre-processing

Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler, Nisheeth K. Vishnoi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show that, unless NP⊆DTIME(2 Poly log(n)), the closest vector problem with pre-processing, for ℓ p norm for any p ≥ 1, is hard to approximate within a factor of (log n) 1/p-ε for any ε > 0. This improves the previous best factor of 3 1/p - ε 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-ε for any ε > 0.

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages216-225
Number of pages10
DOIs
StatePublished - 2005
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Hardness of approximating the closest vector problem with pre-processing'. Together they form a unique fingerprint.

Cite this