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 language||English (US)|
|Number of pages||39|
|State||Published - Oct 13 2003|
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics