Computer Science – Computational Complexity
Scientific paper
2011-12-07
Computer Science
Computational Complexity
Scientific paper
We give several improvements on the known hardness of the unique shortest vector problem. - We give a deterministic reduction from the shortest vector problem to the unique shortest vector problem. As a byproduct, we get deterministic NP-hardness for unique shortest vector problem in the $\ell_\infty$ norm. - We give a randomized reduction from SAT to uSVP_{1+1/poly(n)}. This shows that uSVP_{1+1/poly(n)} is NP-hard under randomized reductions. - We show that if GapSVP_\gamma \in coNP (or coAM) then uSVP_{\sqrt{\gamma}} \in coNP (coAM respectively). This simplifies previously known uSVP_{n^{1/4}} \in coAM proof by Cai \cite{Cai98} to uSVP_{(n/\log n)^{1/4}} \in coAM, and additionally generalizes it to uSVP_{n^{1/4}} \in coNP. - We give a deterministic reduction from search-uSVP_\gamma to the decision-uSVP_{\gamma/2}. We also show that the decision-uSVP is {\bf NP}-hard for randomized reductions, which does not follow from Kumar-Sivakumar \cite{KS01}.
Aggarwal Divesh
Dubey Chandan
No associations
LandOfFree
Improved hardness results for unique shortest vector problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved hardness results for unique shortest vector problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved hardness results for unique shortest vector problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-595601