Paper 2026/1655

Hardness of Euclidean Closest Vector within $n^{1/8-\epsilon}$ and Binary Nearest Codeword within $n^{1/4-\epsilon}$

Abstract

We prove two deterministic inapproximability results. First, for every fixed $\epsilon>0$, Euclidean $\mathrm{GapCVP}^{(2)}$ is NP-hard with gap factor $n^{1/8-\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 [Ope26]. Second, for every fixed $\epsilon>0$, binary nearest codeword and binary syndrome decoding are NP-hard to approximate within $n^{1/4-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the binary block length. This improves the previous $n^{1/200}$ hardness factor in Chapter 7 of the OpenAI report [Ope26].