Hardness of Euclidean Closest Vector Within <em>n</em><sup>1/8−<em>ϵ</em></sup> and Binary Nearest Codeword Within <em>n</em><sup>1/4−<em>ϵ</em></sup>

Source 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 [1]. 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 [1].