Theory of Computing
-------------------
Title : Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
Authors : Ishay Haviv and Oded Regev
Volume : 8
Number : 23
Pages : 513-531
URL : https://theoryofcomputing.org/articles/v008a023
Abstract
--------
We show that unless $NP \subseteq RTIME (2^{\poly(\log{n})})$, there
is no polynomial-time algorithm approximating the Shortest Vector
Problem (SVP) on $n$-dimensional lattices in the $\ell_p$ norm
($1 \leq p < \infty$) to within a factor of $2^{(\log{n})^{1-\epsilon}}$
for any $\epsilon > 0$. This improves the previous best factor of
$2^{(\log{n})^{1/2-\epsilon}}$ under the same complexity assumption due to
Khot (J. ACM, 2005). Under the stronger assumption $NP \nsubseteq
RSUBEXP$, we obtain a hardness factor of $n^{c/\log\log{n}}$ for some
$c>0$.
Our proof starts with Khot's SVP instances that are hard to
approximate to within some constant. To boost the hardness factor we
simply apply the standard tensor product of lattices. The main novel
part is in the analysis, where we show that the lattices of Khot
behave nicely under tensorization. At the heart of the analysis is a
certain matrix inequality which was first used in the context of
lattices by de Shalit and Parzanchevski.