Seth-Hardness of Coding Problems

Abstract: We show that, assuming a common conjecture in complexity theory, there are "no non-trivial algorithms" for the two most important problems in coding theory: the Nearest Codeword Problem (NCP) and the Minimum Distance Problem (MDP). Specifically, for any constant \eps > 0, there is no N^{1-\eps}-time algorithm for codes with N codewords. We also show similar results for variants of these problems, such as approximate versions, NCP with
preprocessing, etc. These results are inspired by earlier work showing similar results for the analogous lattice problems (joint works with Huck Bennett, Sasha Golovnev, and Divesh Aggarwal), but the proofs for coding problems are far simpler.

Based on joint work with Vinod Vaikuntanathan, FOCS 2019