Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.
Has this been derandomized?
$\begingroup$
$\endgroup$
10
-
3$\begingroup$ I think this is still an open problem. Here is a reference from 2012, for example: theoryofcomputing.org/articles/v008a022/v008a022.pdf. This paper from 2014 mentions only randomized reductions arxiv.org/abs/1412.7994 $\endgroup$– Sasho NikolovCommented Nov 21, 2016 at 1:32
-
$\begingroup$ @SashoNikolov thank you. one more small point to clarify. Does the SVP problem inherently have an unique solution or at least just at most a slowly growing number (that is do we have much choice in picking shortest basis upto signs)? $\endgroup$– TurboCommented Nov 21, 2016 at 4:47
-
$\begingroup$ @SashoNikolov 'unique solution upto signs or at least just at most a slowly growing number upto signs'. $\endgroup$– TurboCommented Nov 21, 2016 at 5:19
-
$\begingroup$ In the integer lattice $\mathbb{Z}^n$ the shortest nonzero vectors are the standard basis vectors (and their negations), which is $n$ vectors up to signs. I am not sure what the best upper bound on the number of shortest vectors is. $\endgroup$– Sasho NikolovCommented Nov 21, 2016 at 8:44
-
1$\begingroup$ see for example section 3.4. of this paper by Leech. $\endgroup$– Sasho NikolovCommented Nov 21, 2016 at 13:12
|
Show 5 more comments