Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JIANGTAO MENG:
All reports by Author Jiangtao Meng:

TR06-052 | 15th April 2006
Wenbin Chen, Jiangtao Meng

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

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, ... more >>>




ISSN 1433-8092 | Imprint