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.


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