TY - JOUR
T1 - Improved inapproximability of lattice and coding problems with preprocessing
AU - Regev, Oded
N1 - Funding Information:
Manuscript received May 25, 2003; revised April 13, 2004. This work was supported by the National Science Foundation under Grant CCR-9987845 and performed while the author was with the Institute for Advanced Study, Princeton, NJ. The material in this paper was presented in part at the 18th IEEE Conference on Computational Complexity, Aarhus, Denmark, July 2003.
PY - 2004/9
Y1 - 2004/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=4544250860&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=4544250860&partnerID=8YFLogxK
U2 - 10.1109/TIT.2004.833350
DO - 10.1109/TIT.2004.833350
M3 - Article
AN - SCOPUS:4544250860
VL - 50
SP - 2031
EP - 2037
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
SN - 0018-9448
IS - 9
ER -