PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

Abstract

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 $\epsilon$-balanced codes to derandomize and further simplify their reduction for the case of finite fields.

arXiv admin note: text overlap with arXiv:2410.02636