DocumentCode
1085722
Title
Improved inapproximability of lattice and coding problems with preprocessing
Author
Regev, Oded
Author_Institution
Dept. of Comput. Sci., Tel-Aviv Univ., Ramat-Aviv, Israel
Volume
50
Issue
9
fYear
2004
Firstpage
2031
Lastpage
2037
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.
Keywords
computational complexity; linear codes; optimisation; program processors; NP-hard; closest vector problem; computational complexity; lattice-coding problems; linear codes; n-approximation algorithm; preprocessing; relatively nearest codeword problem; Application software; Approximation algorithms; Computational complexity; Computer science; Cryptography; Decoding; Lattices; Linear code; Polynomials; Vectors; CVP; Closest vector problem; NCP; NP-hardness; RNCP; computational complexity; linear codes; nearest codeword problem; relatively nearest codeword problem;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/TIT.2004.833350
Filename
1327804
Link To Document