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.
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 show that the minimum distance of a linear code (or equivalently, the weight of the lightest codeword) is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. Under the stronger assumption that NP is not contained in RQP (random quasi-polynomial time), we show that the minimum distance is not approximable to within the factor 2/sup log(1-/spl epsiv/)n/, for any /spl epsiv/>0, where n denotes the block length of the code. Our results hold for codes over every finite field, including the special case of binary codes. In the process we show that the nearest codeword problem is hard to solve even under the promise that the number of errors is (a constant factor) smaller than the distance of the code. This is a particularly meaningful version of the nearest codeword problem. Our results strengthen (though using stronger assumptions) a previous result of A. Vardy (1997) who showed that the minimum distance is NP-hard to compute exactly. Our results are obtained by adapting proofs of analogous results for integer lattices due to M. Ajtai (1998) and D. Micciancio (1998). A critical component in the adaptation is our use of linear codes that perform better than random (linear) codes.
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.
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].
Hardness of Approximating Quantum Code Distance Beyond N
We study the computational complexity of approximating the minimum distance of a stabilizer code. Classically, the minimum distance problem is NP-hard to approximate even to within an additive gap linear in the block length. For quantum codes, however, the reductions of Kapshikar and Kundu and of Grigorescu, Jha and Samperton reach only an additive O(N) gap in the block length N. We close this gap and, in a separate direction, initiate the fine-grained study of the problem.
We show that no randomized algorithm approximates the distance to within an additive αN, for a constant α>0, unless NP⊆coRP. In the fine-grained setting, for every ε>0, no randomized 2(1−ε)κpoly(N)-time algorithm computes the distance of a code with κ logical qubits unless SETH falls; and no randomized 2o(N)-time algorithm approximates the distance to within a linear additive gap, on instances where block length, number of logical qubits, and gap are simultaneously linear, unless non-uniform Gap-ETH falls.
The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in F_2^n and a linear space L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance from v. It is well-known that the nearest codeword problem is NP-hard. Therefore approximation algorithms are of interest. The best effcient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio of O(k/c) for an arbitrary constant c; and a randomized algorithm that achieves an approximation ratio of O(k/ log n). In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work, (almost) de-randomizing the randomized algorithm of Berman and Karpinski. We also initiate a study of the following Remote Point Problem (RPP). Given a linear space L in F_2^n of dimension k RPP asks to find a point v in F_2^n that is far from L. We say that an algorithm achieves a remoteness of r for the RPP if it always outputs a point v that is at least r-far from L. In this paper we present a deterministic polynomial time algorithm that achieves a remoteness of Omega(n log k / k) for all k < n/2. We motivate the remote point problem by relating it to both the nearest codeword problem and the matrix rigidity approach to circuit lower bounds in computational complexity theory.
Recently we showed that minimum weight decoding in the (6.6.6 planar) colour code is NP-hard. However, it remained an open question as to whether it was possible to approximate the minimum weight decoding arbitrarily closely in polynomial time. In this paper we prove that it is possible: for any ε>0 there is an polynomial time algorithm that, given a syndrome, can find an error-set generating that syndrome whose weight is at most 1+ε times the weight of the minimum weight decoding. As a consequence we see that, for any ε>0, there is a polynomial time algorithm that can correct all errors of weight up to (1−ε)d/2 in the distance d colour code (so almost up to the theoretical d/2 limit).
The polynomial we give is impractically large, but it does open the door for sensible polynomial time algorithms that approximate minimum weight decoding and, in particular, shows that approximate decoding is not NP-hard.