Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-052 | 15th April 2006 00:00

Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm

RSS-Feed




TR06-052
Authors: Wenbin Chen, Jiangtao Meng
Publication: 21st April 2006 09:47
Downloads: 2965
Keywords: 


Abstract:

We show that the Closest Vector
Problem with Preprocessing over infty Norm
is NP-hard to approximate to within a factor of $(\log
n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their
reductions are based on norm embeddings. However, our reductions are
based on the reduction of Alekhnovich et al. and the property of Hadamard
matrix.



ISSN 1433-8092 | Imprint