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.
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 the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n , of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.
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 ε-balanced codes to derandomize and further simplify their reduction for the case of finite fields.
We prove two deterministic inapproximability results. First, for every fixed 0<ϵ<1/2, Euclidean GapCVP(2) is NP-hard with gap factor n1/2−ϵ 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 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) at gap factor Cn, placing that problem in NP∩coNP for an absolute constant C>0 [AR05]. An NP-hard problem lying in coNP would give NP=coNP, so the factor n1/2−ϵ above cannot be improved to Cn unless the two classes coincide. Second, for every fixed 0<ϵ<1, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor n1−ϵ 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 n1/200 hardness factor in Chapter 7 of the OpenAI report [Ope26].