pdf icon
Volume 8 (2012) Article 22 pp. 487-512
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction
Received: May 12, 2011
Published: September 24, 2012
Download article from ToC site:
[PDF (315K)]    [PS (1284K)]    [PS.GZ (339K)]
[Source ZIP]
Keywords: lattices, shortest vector problem, NP-hardness, hardness of approximation, randomized reductions
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time randomized reductions with one-sided error that produce no false positives. We also prove inapproximability for quasi-polynomial factors under the same kind of reductions running in subexponential time. Previous hardness results for SVP either incurred two-sided error, or only proved hardness for small constant approximation factors. Close similarities between our reduction and recent results on the complexity of the analogous problem on linear codes make our new proof an attractive target for derandomization, paving the road to a possible NP-hardness proof for SVP under deterministic polynomial time reductions.