Under the auspices of the Computational Complexity Foundation (CCF)

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

TR97-059
Authors: Jin-Yi Cai, Ajay Nerurkar
Publication: 23rd December 1997 10:36
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