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• 0 citations

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

Inapproximability of the shortest vector problem: Toward a deterministic reduction

Daniele Micciancio

Oct 9, 20132 citations

Hardness of approximating the shortest vector problem in lattices

Subhash Khot

Journal of the ACMSep 1, 2005211 citations

Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

Ishay Haviv, Oded Regev

arXiv:1806.04087Theory of ComputingJan 1, 201248 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, 200784 citations

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

Zhao Song

Sep 2, 20260 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 complexityJan 1, 20060 citations

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}$ 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• 0 citations

arXiv HTML PDF

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

Inapproximability of the shortest vector problem: Toward a deterministic reduction

Daniele Micciancio

Abstract: We prove that the Shortest Vector Problem (SVP) on point lattices is NPhard to approximate for any constant factor under polynomial-time randomized reductions with one-sided error that produce no false positives. We also prove inapproximability for quasi-polynomial factors under the same kind of reductions running in subexponential time. Previous hardness results for SVP either incurred two-sided error, or only proved hardness for small constant approximation factors. Close similarities between our reduction and recent results on the complexity of the analogous problem for linear codes make our new proof an attractive target for derandomization, paving the road to a possible NP-hardness proof for SVP under deterministic polynomial-time reductions.Abstract: We prove that the Shortest Vector Problem (SVP) on point lattices is NPhard to approximate for any constant factor under polynomial-time randomized reductions with one-sided error that produce no false positives. We also prove inapproximability for quasi-polynomial factors under the same kind of reductions running in subexponential time. Previous hardness results for SVP either incurred two-sided error, or only proved hardness for small constant approximation factors. Close similarities between our reduction and recent results on the complexity of the analogous problem for linear codes make our new proof an attractive target for derandomization, paving the road to a possible NP-hardness proof for SVP under deterministic polynomial-time reductions.

Oct 9, 20132 citations

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-ϵ .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 ACMSep 1, 2005211 citations

Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

Ishay Haviv, Oded Regev

$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\poly}{\mathop{\mathrm{poly}}} \newcommand{\eps}{\varepsilon} $ We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, there is no polynomial-time algorithm approximating the Shortest Vector Problem ($\SVP$) on $n$ -dimensional lattices in the $\ell_p$ norm ( $1 \leq p<\infty$ ) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps >0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of $n^{c/\log\log{n}}$ for some $c>0$ . Our proof starts with Khot's $\SVP$ instances that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of Khot behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\poly}{\mathop{\mathrm{poly}}} \newcommand{\eps}{\varepsilon} $ We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, there is no polynomial-time algorithm approximating the Shortest Vector Problem ($\SVP$) on $n$-dimensional lattices in the $\ell_p$ norm ($1 \leq p<\infty$) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps >0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of $n^{c/\log\log{n}}$ for some $c>0$. Our proof starts with Khot's $\SVP$ instances that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of Khot behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.

arXiv:1806.04087Theory of ComputingJan 1, 201248 citations

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

Ishay Haviv, Oded Regev

ACM Symposium on Theory of Computing (STOC)Jun 11, 200784 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].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, 20260 citations

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

Wenbin Chen, Jiangtao Meng

Electronic colloquium on computational complexityJan 1, 20060 citations

SVP

_p

is Deterministically NP-Hard for all

p > 2

, Even to Approximate Within a Factor of

2^{\log^{1-\varepsilon} n}

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

n

-dimensional lattices in the

\ell_p

norm (

1 \leq p<\infty

) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps >0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of

n^{c/\log\log{n}}

for some

c>0

. Our proof starts with Khot's $\SVP$ instances that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of Khot behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.

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].