Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sauer's Lemma:
TR97-047 | 20th October 1997
Miklos Ajtai

The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

We show that the shortest vector problem in lattices
with L_2 norm is NP-hard for randomized reductions. Moreover we
also show that there is a positive absolute constant c, so that to
find a vector which is longer than the shortest non-zero vector by no
more than a factor of ... more >>>

ISSN 1433-8092 | Imprint