Deterministic Hardness of Approximation For SVP in all Finite ${\mathrm{\ell }}_p$ Norms

We show that, assuming NP $\subseteq ̸$ ${\cap }_{\delta >0}$DTIME$(\exp n^{\delta })$, the shortest vector problem for lattices of rank $n$ in any finite ${\mathrm{\ell }}_p$ norm is hard to approximate within a factor of $2^{(\log n{)}^{1-o(1)}}$, via a deterministic reduction. Previously, for the Euclidean case $p=2$, even hardness of the exact shortest vector problem was not known under a deterministic reduction.