Euclidean SVP is deterministically NP-hard to approximate within any constant factor

Technical Summary: Deterministic NP-Hardness of Euclidean SVP Approximation

Problem Statement
The paper addresses the computational complexity of the Euclidean Shortest Vector Problem (SVP). Specifically, it investigates the $\rho$-GapSVP problem: given an integral lattice basis and a threshold $d$, distinguish between the case where the shortest non-zero vector has length $\lambda_2(L) \le d$ (YES) and the case where $\lambda_2(L) > \rho d$ (NO), for a constant approximation factor $\rho > 1$.

Prior to this work, the deterministic NP-hardness of approximating Euclidean SVP was limited to factors $\rho < \sqrt{2}$. While randomized reductions established hardness for arbitrary constant factors (Khot [22]) and even almost-polynomial factors (Haviv and Regev [19]), the derandomization of these results for Euclidean space remained an open challenge for over a decade. The Euclidean norm's lack of multiplicative properties under tensor products, unlike the Hamming distance in coding theory, was a primary obstacle.

Methodology
The author constructs a deterministic polynomial-time many-one reduction from an NP-complete problem to Euclidean $\rho$-GapSVP for any constant $\rho > 1$. The proof strategy relies on three main components:

1. Deterministic Binary $\ell_1$ Gap Construction:
   The author first constructs a lattice with a "binary gap" in the $\ell_1$ norm. They combine a deterministic reduction from Gap Exact Set Cover with a Reed–Solomon locally dense lattice gadget.

   • The Set Cover reduction (based on Micciancio [27] and Bennett–Peikert [9]) creates a source instance where YES instances yield a binary vector with low weight, while NO instances force all non-zero integer vectors to have high support.
   • The Reed–Solomon gadget (derived from the author's previous work [36]) ensures that for any prescribed binary projection, there exists a lattice vector in a specific coset that is binary and has an $\ell_1$ norm slightly above half the lattice's minimum.
   • By combining these via a block embedding, they produce a lattice $L$ and threshold $d$ such that:
     • YES: There exists a binary vector $y \in L \cap \{0,1\}^N$ with $\|y\|_1 < d$.
     • NO: For all non-zero $x \in L$, $\|x\|_1 \ge \eta d$, where $1 < \eta < 2$ is a fixed constant.

2. Exact $\ell_1$ Tensor Identity:
   A critical theoretical contribution is the proof that the minimum $\ell_1$ norm of an integral lattice is multiplicative under tensor products.

   • Unlike the Euclidean norm ($\ell_2$), where the shortest vector in a tensor product lattice $L_1 \otimes L_2$ need not be a pure tensor (and thus $\lambda_2(L_1 \otimes L_2) \neq \lambda_2(L_1)\lambda_2(L_2)$), the $\ell_1$ minimum satisfies the exact identity:
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • This result is established by relating the $\ell_1$ minimum of a lattice to the minimum Lee weight of a quotient code over integer residue rings. The author utilizes the Ojiro–Matsui product formula for Lee weights [29] to prove this multiplicativity for full-rank lattices and extend it to arbitrary rank lattices via a completion argument.

3. Tensor Amplification:
   The author takes the $t$-fold tensor power of the base lattice $L$ constructed in step 1.

   • In the YES case, the vector $y^{\otimes t}$ remains binary. Since binary vectors satisfy $\|v\|_2^2 = \|v\|_1$, the Euclidean length becomes $\|y^{\otimes t}\|_2 = \|y\|_1^{t/2} < d^{t/2}$.
   • In the NO case, the multiplicative property of the $\ell_1$ norm ensures $\lambda(L^{\otimes t}) = \lambda(L)^t \ge (\eta d)^t$. Using the inequality $\|x\|_2 \ge \|x\|_1^{1/2}$ (for integer vectors), the Euclidean length is bounded below by $(\eta d)^{t/2}$.
   • The resulting approximation gap is $\eta^{t/2}$. By choosing a sufficiently large constant $t$, the gap can exceed any desired constant $\rho$.

Key Results

• Theorem 1.2 (Main Theorem): For every constant $\rho > 1$, Euclidean $\rho$-GapSVP is NP-hard under a deterministic polynomial-time many-one reduction. This provides a deterministic counterpart to Khot's randomized theorem.
• Theorem 1.4 (All Finite Norms): The result extends to all fixed finite $\ell_p$ norms ($1 \le p < \infty$). For any fixed $p$ and constant $\rho > 1$, $\rho$-GapSVP$_p$ is deterministically NP-hard.
• Theorem 1.5 (Dimension-Dependent Regimes): By allowing the tensor order $t$ to grow with the input size (rather than being a fixed constant), the author derives deterministic versions of the dimension-dependent hardness regimes previously known only for randomized reductions:
  • Quasipolynomial-time reductions: Hardness for factors $2^{(\log n)^{1-\varepsilon}}$.
  • Subexponential-time reductions: Hardness for factors $n^{c/\log \log n}$.

Significance and Claims
The paper claims to resolve a long-standing open problem in lattice-based complexity by removing the need for randomness in proving the NP-hardness of approximating Euclidean SVP for arbitrary constant factors.

• Derandomization: The work successfully derandomizes the reduction for Euclidean SVP, a task that resisted previous attempts due to the difficulty of constructing deterministic locally dense lattices in Euclidean space.
• Methodological Shift: The proof does not attempt to derandomize Khot's construction line-by-line. Instead, it introduces a new structural approach: using a deterministic binary gadget to create an $\ell_1$ gap, and then leveraging the exact multiplicativity of the $\ell_1$ norm under tensor products to amplify this gap into the Euclidean domain.
• Coding Theory Analogy: The paper highlights a deep connection between lattice problems and coding theory. Just as the minimum Hamming distance of linear codes is multiplicative under tensor products, the author shows that the minimum $\ell_1$ norm of integral lattices (via the Lee metric) shares this property, allowing the transfer of amplification techniques from coding theory to lattices.
• Comparison to Prior Work: The author notes that while Hair and Sahai [18] recently obtained deterministic hardness for arbitrary constants, their result relied on a PCP approach and subexponential-time reductions. This paper improves upon that by achieving the result via polynomial-time reductions.

The paper concludes that while the tensor amplification method has a natural ceiling (yielding factors of $n^{o(1)}$ rather than $n^\varepsilon$ for fixed $\varepsilon$), it successfully establishes the deterministic hardness of constant-factor approximation for Euclidean SVP and all finite $\ell_p$ norms.