The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm
Weijian Chen, J. Meng · IEEE Transactions on Information Theory · 2006
We show that the closest vector problem with preprocessing (CVPP) over$ell_infty$norm$(hboxCVPP_infty)$is NP-hard. The result is obtained by the reduction from the subset sum problem with preprocessing to$hbox CVPP_infty$. The reduction also shows the NP-hardness of$hbox CVP_infty$, which is much simpler than all previously known proofs. In addition, we also give a direct reduction from exact 3-sets cover problem to$hbox CVPP_infty$.