PCP-free Inapproximability of Nearest Codeword and Minimum Distance

We present simple deterministic gap-producing reductions from the canonical NP-hard problem of solving systems of quadratic equations to the approximate versions of the Nearest Codeword Problem and the Minimum Distance Problem—achieving inapproximability within arbitrary constant factors. Our reductions and proofs are short and simple, relying primarily on linear codes in which all codewords have roughly equal weight.

Based on joint work with Vijay Bhattiprolu, Venkat Guruswami, and Euiwoong Lee.