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 the results of Feige and Micciancio in [10]. 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) |
|---|---|
| Title of host publication | Proceedings of the Annual IEEE Conference on Computational Complexity |
| Pages | 363-370 |
| Number of pages | 8 |
| State | Published - 2003 |
| Event | 18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark Duration: Jul 7 2003 → Jul 10 2003 |
Other
| Other | 18th Annual IEEE Conference on Computational Complexity |
|---|---|
| Country/Territory | Denmark |
| City | Aarhus |
| Period | 7/7/03 → 7/10/03 |
ASJC Scopus subject areas
- Computational Mathematics