Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.

Has this been derandomized?

  • 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$ 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$
    – Turbo
    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$
    – Turbo
    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$ Nov 21, 2016 at 8:44
  • 1
    $\begingroup$ see for example section 3.4. of this paper by Leech. $\endgroup$ Nov 21, 2016 at 13:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.