Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > AJAY NERURKAR:
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

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




ISSN 1433-8092 | Imprint