Approximating CVP to within almost-polynomial factors is NP-hard

I. Dinur, G. Kindler, R. Raz, S. Safra

Research output: Contribution to journalArticlepeer-review

93 Scopus citations


This paper shows the problem of finding the closest vector in an n-dimensional lattice to be NP-hard to approximate to within factor nc/log log n for some constant c>0.

Original languageEnglish (US)
Pages (from-to)205-243
Number of pages39
Issue number2
StatePublished - 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'Approximating CVP to within almost-polynomial factors is NP-hard'. Together they form a unique fingerprint.

Cite this