Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-016 | 24th March 1998 00:00

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

RSS-Feed




TR98-016
Authors: Daniele Micciancio
Publication: 30th March 1998 18:09
Downloads: 2170
Keywords: 


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.



ISSN 1433-8092 | Imprint