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$ – Sasho Nikolov Nov 21 '16 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$ – Brout Nov 21 '16 at 4:47
  • $\begingroup$ @SashoNikolov 'unique solution upto signs or at least just at most a slowly growing number upto signs'. $\endgroup$ – Brout Nov 21 '16 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 Nikolov Nov 21 '16 at 8:44
  • 1
    $\begingroup$ see for example section 3.4. of this paper by Leech. $\endgroup$ – Sasho Nikolov Nov 21 '16 at 13:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.