2 log1-εn hardness for the closest vector problem with preprocessing

Subhash A. Khot, Preyas Popat, Nisheeth K. Vishnoi

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

Abstract

We prove that for an arbitrarily small constant ε > 0, assuming NP⊈DTIME (2 log O(1-εn), the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than 2 log 1-ε n. This improves upon the previous hardness factor of (log n) δ for some δ > 0 due to [AKKV05].

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages277-288
Number of pages12
DOIs
StatePublished - 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

Keywords

  • PCP
  • closest vector problem
  • hardness of approximation
  • lattices
  • nearest codeword problem

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of '2 <sup>log1-εn</sup> hardness for the closest vector problem with preprocessing'. Together they form a unique fingerprint.

  • Cite this

    Khot, S. A., Popat, P., & Vishnoi, N. K. (2012). 2 log1-εn hardness for the closest vector problem with preprocessing. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 277-288). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214004