5
$\begingroup$

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

Has this been derandomized?

$\endgroup$
  • 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$ – T.... 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$ – T.... 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.