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

Isaac M. Hair, Amit Sahai

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 Kar…