The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm |
| |
| Authors: | Chen W Jiangtao Meng |
| |
| Affiliation: | Dept. of Comput. Sci., Nanjing Univ.; |
| |
| 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: | |
|
|
