SVP_p is Deterministically NP-Hard for all p > 2, Even to Approximate Within a Factor of 2^log^1-ε n

2025/11/06 by Isaac M. Hair, Amit Sahai, Hair, Isaac M. +1
Computer Science · #Complexity and Algorithms in Graphs #Stochastic Gradient Optimization Techniques #Computational Geometry and Mesh Generation

paper · pdf · doi:10.48550/arxiv.2511.04125

Abstract

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 \not ⊆ 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.

Citations

• Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
• Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
• Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms
• Analytical Approach to Parallel Repetition
• On lattices, learning with errors, random linear codes, and cryptography
• Minkowski's Convex Body Theorem and Integer Programming
• Integer Programming with a Fixed Number of Variables
• Factoring polynomials with rational coefficients

Related

• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓ_p norms for p>2
• Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms
• NP-hardness of SVP in Euclidean Space
• Slide Reduction, Revisited---Filling the Gaps in SVP Approximation
• Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)