Abstract
We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within √3-ε for any ε > 0. In addition, we show that the nearest codeword problem with preprocessing (NCPP) is NP-hard to approximate to within 3 - ε. These results improve previous results of Feige and Micciancio. We also present the first inapproximability result for the relatively nearest codeword problem with preprocessing (RNCP). Finally, we describe an n-approximation algorithm to CVPP.
Original language | English (US) |
---|---|
Pages (from-to) | 2031-2037 |
Number of pages | 7 |
Journal | IEEE Transactions on Information Theory |
Volume | 50 |
Issue number | 9 |
DOIs | |
State | Published - Sep 2004 |
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Library and Information Sciences