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

Abstract

We show that, assuming NP $⊈$ ${\cap }_{\delta >0}$DTIME$\left(\exp n^{\delta }\right)$, the shortest vector problem for lattices of rank $n$ in any finite ${\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.

Updated acknowledgments