Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.04125

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

Isaac M. Hair, Amit Sahai

Published Nov 6, 2025• 2 citations
arXivHTMLPDF

Abstract

We prove that SVP$_p$ is NP-hard to approximate within a factor of $2^{\log^{1 - \varepsilon} n}$, for all constants $\varepsilon > 0$ and $p > 2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{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 $\not \subseteq$ 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 \emph{regularized} PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.

DOI
10.48550/arxiv.2511.04125

Related papers

Hardness of approximating the shortest vector problem in lattices

Subhash Khot

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓ p norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2 poly (log n ) ), we show that there is no polynomial-time algorithm with approximation ratio 2 (log n ) 1/2−ϵ where n is the dimension of the lattice and ϵ > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves some constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product , a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2 (log n ) 1/2-ϵ .

Journal of the ACM•Sep 1, 2005•222 citations

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Ishay Haviv, Oded Regev

We show that unless NP ⊆ RTIME (2poly(log n)), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices inthe lp norm (1 ≤q p<∞) to within a factor of 2(log n)1-ε. This improves the previous best factor of 2(logn)1/2-ε under the same complexity assumption due to Khot. Under the stronger assumption NP ࣰ RSUBEXP, we obtain a hardness factor of nc/log log n for some c > 0.

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•88 citations

Hardness of Euclidean Closest Vector Within n1/2−ϵ and Binary Nearest Codeword Within n1−ϵ

Zhao Song

We prove two deterministic inapproximability results. First, for every fixed $0<\epsilon<1/2$, Euclidean $\mathrm{GapCVP}^{(2)}$ is NP-hard with gap factor $n^{1/2-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the lattice rank. Consequently, the Euclidean closest vector problem is NP-hard to approximate within the same factor. This improves the previous $n^{1/400}$ hardness factor in Chapter 7 of the OpenAI report [Ope25]. Aharonov and Regev gave short certificates for both the YES and the NO case of $\operatorname{GapCVP}^{(2)}$ at gap factor \( C\sqrt n \), placing that problem in $\mathrm{NP}\cap\mathrm{coNP}$ for an absolute constant $C>0$ [AR05]. An NP-hard problem lying in $\mathrm{coNP}$ would give $\mathrm{NP}=\mathrm{coNP}$, so the factor $n^{1/2-\epsilon}$ above cannot be improved to \( C\sqrt n \) unless the two classes coincide. Second, for every fixed $0<\epsilon<1$, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor $n^{1-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the binary block length. Consequently, both optimization problems are NP-hard to approximate within the same factor. This improves the previous $n^{1/200}$ hardness factor in Chapter 7 of the OpenAI report [Ope26].

•Sep 2, 2026•0 citations

Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm.

Wenbin Chen, Jiangtao Meng

We show that the Closest Vector Problem with Preprocessing over `∞ norm (CVPP∞) is NP-hard to approximate to within a factor of (log n)1/2− , unless NP⊆ DTIME (2polylog(n)). The result is the same as that in [19] by Regev and Rosen, but our proof methods are different from theirs. Their reductions are based on norm embeddings. However, our reductions are based on the reduction of [2] and the property of Hadamard matrix.

Electronic colloquium on computational complexity•Jan 1, 2006•0 citations

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren

We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (and almost-polynomial factors assuming NP cannot be solved in quasipolynomial time). The starting point is a simple NP-hardness result without a gap, and is thus "PCP-free." Our approach is inspired by that of Bhattiprolu and Lee [BL24] who give a PCP-free randomized reduction for similar problems over the integers and the reals. We leverage the existence of $\varepsilon$-balanced codes to derandomize and further simplify their reduction for the case of finite fields.

arXiv:2503.11131•Mar 14, 2025•1 citation

Approximating-CVP to within almost-polynomial factors is NP-hard

Irit Dinur, Guy Kindler, Muli Safra

This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to 2/sup (logn)1-4/ where /spl epsiv/=(loglogn)/sup -c/ for any constant c< 1/2.

Annual Symposium on Foundations of Computer Science•Nov 27, 2002•60 citations
SVPp_pp​ is Deterministically NP-Hard for all p>2p > 2p>2, Even to Approximate Within a Factor of 2log⁡1−εn2^{\log^{1-\varepsilon} n}2log1−εn
We prove that SVPp_pp​ is NP-hard to approximate within a factor of 2log⁡1−εn2^{\log^{1 - \varepsilon} n}2log1−εn, for all constants ε>0\varepsilon > 0ε>0 and p>2p > 2p>2, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVPp_pp​ is NP-hard in a finite ℓp\ell_pℓp​ norm. Hardness for SVPp_pp​ with ppp finite was previously only known if NP ⊈\not \subseteq⊆ 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, SVPp_pp​ is NP-hard to approximate within a small polynomial factor, for all constants p>2p > 2p>2. Our proof techniques are surprisingly elementary; we reduce from a \emph{regularized} PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.
Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓ p norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2 poly (log n ) ), we show that there is no polynomial-time algorithm with approximation ratio 2 (log n ) 1/2−ϵ where n is the dimension of the lattice and ϵ > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves some constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product , a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2 (log n ) 1/2-ϵ .
We prove two deterministic inapproximability results. First, for every fixed 0<ϵ<1/20<\epsilon<1/20<ϵ<1/2, Euclidean GapCVP(2)\mathrm{GapCVP}^{(2)}GapCVP(2) is NP-hard with gap factor n1/2−ϵn^{1/2-\epsilon}n1/2−ϵ under deterministic polynomial-time many-one reductions, where nnn denotes the lattice rank. Consequently, the Euclidean closest vector problem is NP-hard to approximate within the same factor. This improves the previous n1/400n^{1/400}n1/400 hardness factor in Chapter 7 of the OpenAI report [Ope25]. Aharonov and Regev gave short certificates for both the YES and the NO case of GapCVP⁡(2)\operatorname{GapCVP}^{(2)}GapCVP(2) at gap factor Cn C\sqrt n Cn​, placing that problem in NP∩coNP\mathrm{NP}\cap\mathrm{coNP}NP∩coNP for an absolute constant C>0C>0C>0 [AR05]. An NP-hard problem lying in coNP\mathrm{coNP}coNP would give NP=coNP\mathrm{NP}=\mathrm{coNP}NP=coNP, so the factor n1/2−ϵn^{1/2-\epsilon}n1/2−ϵ above cannot be improved to Cn C\sqrt n Cn​ unless the two classes coincide. Second, for every fixed 0<ϵ<10<\epsilon<10<ϵ<1, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor n1−ϵn^{1-\epsilon}n1−ϵ under deterministic polynomial-time many-one reductions, where nnn denotes the binary block length. Consequently, both optimization problems are NP-hard to approximate within the same factor. This improves the previous n1/200n^{1/200}n1/200 hardness factor in Chapter 7 of the OpenAI report [Ope26].
We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (and almost-polynomial factors assuming NP cannot be solved in quasipolynomial time). The starting point is a simple NP-hardness result without a gap, and is thus "PCP-free." Our approach is inspired by that of Bhattiprolu and Lee [BL24] who give a PCP-free randomized reduction for similar problems over the integers and the reals. We leverage the existence of ε\varepsilonε-balanced codes to derandomize and further simplify their reduction for the case of finite fields.