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