Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-020 | 1st May 2012 18:06

Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

RSS-Feed




Revision #1
Authors: Daniele Micciancio
Accepted on: 1st May 2012 18:06
Downloads: 3633
Keywords: 


Abstract:

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.



Changes to previous version:

Fixed some bugs and improved presentation.


Paper:

TR12-020 | 3rd March 2012 02:56

Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction


Abstract:

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time reverse unfaithful random reductions. These are probabilistic reductions with one-sided error that produce false negatives with small probability, but are guaranteed not to produce false positives regardless of the value of the randomness used in the reduction process. 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 2-sided error, or only proved hardness for some small constant approximation factors. Close similarities between our reduction and recent results on the complexity of analogous problems 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.



ISSN 1433-8092 | Imprint