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

Abstract

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