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