__
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

**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$.