About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1998
Conference paper
Shortest vector problem in L2 is NP-hard for randomized reductions
Abstract
We show that the shortest vector problem in lattices with L2. norm is NP-hard for randomized reductions. Moreover we also show that there is an absolute constant ε>0 so that to find a vector which is longer than the shortest non-zero vector by no more than a factor of 1+2-n(ε) (with respect to the L2 norm) is also NP-hard for randomized reductions. The corresponding decision problem is NP-complete for randomized reductions.