We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within /spl radic/3-/spl epsi/ for any /spl epsi/>0. In addition, we show that the nearest codeword problem with preprocessing (NCPP) is NP-hard to approximate to within 3-/spl epsi/. 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.
No takes yet. Share an insight, caveat, or question.
Oded Regev (2004) studied this question.
Synapse has enriched 4 closely related papers on similar clinical questions. Consider them for comparative context: