SVPp Is Deterministically NP-Hard for All p > 2, Even to Approximate within a Factor of 2log1-εn

We prove that SVP p is NP-hard to approximate within a factor of 2 log 1-ε n , for all constants ε > 0 and p > 2, under standard deterministic Karp reductions. This result is also the first proof that exact SVP p is NP-hard in a finite ℓ 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 regularized PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.