Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-052 | 15th April 2006 00:00

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

TR06-052
Authors: Wenbin Chen, Jiangtao Meng
Publication: 21st April 2006 09:47
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