DocumentCode
1683567
Title
Improved inapproximability of lattice and coding problems with preprocessing
Author
Regev, Oded
Author_Institution
Inst. for Adv. Study, Princeton, NJ, USA
fYear
2003
Firstpage
363
Lastpage
370
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 (2002). 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; cryptography; linear codes; polynomial approximation; probability; set theory; vectors; NP-hard problem; closest vector problem with preprocessing; coding problem; cryptography; inapproximability; lattice problem; linear code; n-approximation algorithm; nearest codeword problem with preprocessing; polynomial-time approximation; probability; relatively nearest codeword problem with preprocessing; Application software; Approximation algorithms; Codes; Computer science; Cryptography; Decoding; Encoding; Lattices; Polynomials; Vectors;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
ISSN
1093-0159
Print_ISBN
0-7695-1879-6
Type
conf
DOI
10.1109/CCC.2003.1214435
Filename
1214435
Link To Document