__
TR98-016 | 24th March 1998 00:00
__

#### The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.

**Abstract:**
We show that computing the approximate length of the shortest vector

in a lattice within a factor c is NP-hard for randomized reductions

for any constant c<sqrt(2). We also give a deterministic reduction

based on a number theoretic conjecture.