All reports by Author Ajay Nerurkar:

__
TR97-059
| 22nd December 1997
__

Jin-Yi Cai, Ajay Nerurkar#### 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

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