# The shortest vector problem is NP-hard to approximate to
within some constant

**Author:** Daniele Micciancio

SIAM Journal
on Computing, **30**(6):2008-2035 (March
2001)

[BibTeX] [PostScript] [PDF] [doi:10.1137/S0097539700373039]

**Abstract:** We show that approximating the
*shortest vector problem* (in any *Lp* norm) to
within any constant factor less than *2^{1/p}* is hard for
NP under *reverse unfaithful random* reductions with
inverse polynomial error probability. In particular,
approximating the *shortest vector problem* is not in RP
(random polynomial time), unless NP equals RP. We also prove a
proper NP-hardness result (i.e., hardness under deterministic
many-one reductions) under a reasonable number theoretic
conjecture on the distribution of square-free smooth numbers. As
part of our proof, we give an alternative construction of Ajtai's
constructive variant of Sauer's lemma, that greatly simplifies
Ajtai's original proof.

## Notes

Preliminary versions:
MIT/LCS/TM-574,
ECCC TR98-016, and
FOCS 1998
(Machtey Award for best student paper).