Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-059 | 22nd December 1997 00:00

Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

RSS-Feed




TR97-059
Authors: Jin-Yi Cai, Ajay Nerurkar
Publication: 23rd December 1997 10:36
Downloads: 1035
Keywords: 


Abstract:

Recently Ajtai showed that
to approximate the shortest lattice vector in the $l_2$-norm within a
factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large
constant $k$, is NP-hard under randomized reductions.
We improve this result to show that
to approximate a shortest lattice vector within a
factor $(1+ \mbox{dim}^{-\epsilon})$, for any
$\epsilon>0$, is NP-hard under randomized reductions.
Our proof also works for arbitrary $l_p$-norms, $1 \leq p < \infty$.



ISSN 1433-8092 | Imprint