SVP${}_p$ is Deterministically NP-Hard for all $p>2$, Even to Approximate Within a Factor of $2^{{\log }^{1-\epsilon }n}$

Abstract

We prove that SVP${}_p$ is NP-hard to approximate within a factor of $2^{{\log }^{1-\epsilon }n}$, for all constants $\epsilon >0$ and $p>2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVP${}_p$ is NP-hard in a finite ${\ell }_p$ norm. Hardness for SVP${}_p$ with $p$ finite was previously only known if NP $⊈$ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVP${}_p$ is NP-hard to approximate within a small polynomial factor, for all constants $p>2$. Our proof techniques are surprisingly elementary; we reduce from a \emph{regularized} PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.