Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CVP:
Reports tagged with CVP:
TR98-048 | 6th July 1998
Irit Dinur, Guy Kindler, Shmuel Safra

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

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}$.

more >>>

ISSN 1433-8092 | Imprint