39th Annual Symposium on Foundations of Computer Science The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant Palo Alto, California November 08-November 11 ISBN: 0-8186-9172-7
We show the shortest vector problem in the l_2 norm is NP-hard (for randomized reductions) to approximate within any constant factor less than sqrt(2). We also give a deterministic reduction under a reasonable number theoretic conjecture. Analogous results hold in any l_p norm (p>=1). In proving our NP-hardness result, we give an alternative construction satisfying Ajtai's probabilistic variant of Sauer's lemma, that greatly simplifies Ajtai's original proof.
Index Terms:
shortest vector problem, lattices, non-approximability, Sauer's lemma
Citation:
Daniele Micciancio, "The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant," focs, pp.92, 39th Annual Symposium on Foundations of Computer Science, 1998 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb