Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-048 | 6th July 1998 00:00

#### Approximating CVP to Within Almost Polynomial Factor is NP-Hard

TR98-048
Authors: Irit Dinur, Guy Kindler, Shmuel Safra
Publication: 25th August 1998 16:25
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