Hardness of Approximating the Closest Vector Problem with Pre-Processing

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

Research output: Contribution to journalArticlepeer-review

Abstract

We show that the pre-processing versions of the closest vector problem and the nearest codeword problem are NP-hard to approximate within any constant factor.

Original languageEnglish (US)
Pages (from-to)741-753
Number of pages13
JournalComputational Complexity
Volume20
Issue number4
DOIs
StatePublished - Dec 2011

Keywords

  • Lattices
  • approximation
  • codes
  • hardness
  • preprocessing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

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