Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

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\le p<\infty$) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps > 0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ 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 novelty 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 (2006).

arXiv commentPublished in Theory of Computing, Volume 8 (2012), Article 23; Received: August 26, 2011, Published: September 25, 2012

Cited by in corpus (5)

• (Gap/S)ETH Hardness of SVP
• On the Closest Vector Problem with a Distance Guarantee
• The Projection Games Conjecture and the Hardness of Approximation of super-SAT and related problems
• Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in ${\ell }_p$ norm
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum $k$-Coverage, Unique Set Cover and Related Problems (via $t$-Wise Agreement Testing Theorem)