ECCC-Report TR97-059https://eccc.weizmann.ac.il/report/1997/059Comments and Revisions published for TR97-059en-usTue, 23 Dec 1997 10:36:03 +0200
Paper TR97-059
| Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions |
Jin-Yi Cai,
Ajay Nerurkar
https://eccc.weizmann.ac.il/report/1997/059Recently 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$.
Tue, 23 Dec 1997 10:36:03 +0200https://eccc.weizmann.ac.il/report/1997/059