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

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

Research output: Contribution to journalArticlepeer-review

78 Scopus citations

Abstract

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
JournalCombinatorica
Volume23
Issue number2
DOIs
StatePublished - Oct 13 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

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

Cite this