ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-048 | 6th July 1998 00:00

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

RSS-Feed




TR98-048
Authors: Irit Dinur, Guy Kindler, Shmuel Safra
Publication: 25th August 1998 16:25
Downloads: 1056
Keywords: 


Abstract:

This paper shows finding the closest vector in a lattice
to be NP-hard to approximate to within any factor up to
$2^{(\log{n})^{1-\epsilon}}$ where
$\epsilon = (\log\log{n})^{-\alpha}$
and $\alpha$ is any positive constant $<{1\over 2}$.



ISSN 1433-8092 | Imprint