Seth-Hardness of Coding Problems


Noah Stephens-Davidowitz


Quanquan Liu, Sitan Chen, Nikhil Vyas
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