Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Improved hardness results for unique shortest vector problem   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}.

4
The categories of this paper are: cond-mat
21
The categories of this paper are: adap-org
32
The categories of this paper are: atom-ph
29
The categories of this paper are: funct-an
36
The categories of this paper are: cmp-lg
6
The categories of this paper are: astro-ph
19
The categories of this paper are: eess
28
The categories of this paper are: alg-geom
30
The categories of this paper are: q-alg
12
The categories of this paper are: nucl-th
24
The categories of this paper are: dg-ga
25
The categories of this paper are: patt-sol
16
The categories of this paper are: stat
34
The categories of this paper are: chem-ph
18
The categories of this paper are: econ
8
The categories of this paper are: hep-ex