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


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
Issue number4
StatePublished - Dec 2011


  • Lattices
  • approximation
  • codes
  • hardness
  • preprocessing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Hardness of Approximating the Closest Vector Problem with Pre-Processing'. Together they form a unique fingerprint.

Cite this