DocumentCode :
771652
Title :
The Hardness of the Closest Vector Problem With Preprocessing Over 
Norm
NormAuthor :
Chen, Wenbin ; Meng, Jiangtao
Author_Institution :
Dept. of Comput. Sci., Nanjing Univ.
Volume :
52
Issue :
10
fYear :
2006
Firstpage :
4603
Lastpage :
4606
Abstract :
We show that the closest vector problem with preprocessing (CVPP) over lscr infin norm (CVPPinfin) is NP-hard. The result is obtained by the reduction from the subset sum problem with preprocessing to CVPPinfin. The reduction also shows the NP-hardness of CVPinfin, which is much simpler than all previously known proofs. In addition, we also give a direct reduction from exact 3-sets cover problem to CVPPinfin
Keywords :
computational complexity; optimisation; telecommunication computing; CVPP; NP-hardness; closest vector problem; linfinnorm; preprocessing; Automatic control; Complexity theory; Computational complexity; Computer science; History; Lattices; Mathematics; Polynomials; Public key cryptography; Traveling salesman problems; Closest vector problem; NP-hardness; computational complexity; exact 3-sets cover; polynomial hierarchy; subset sum;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2006.881835
Filename :
1705016
Link To Document :
