We prove that SVP_p is NP-hard to approximate within a factor of 2^{log^{1 - eps} n}, for all constants eps > 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 ell_p norm. Hardness for SVP_p with p finite was previously only known if NP is not contained in 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.
Isaac Hair is an undergraduate at UCSB, currently conducting research in cryptography with Prof. Amit Sahai at UCLA.