Back to TGINF

# Seth-hardness of coding problems

Speaker: Noah Stephens-Davidowitz
Title: Seth-hardness of coding problems
Date: 21 Oct 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Food: TBD

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 $\epsilon > 0$, there is no $N^{1-\epsilon}$-time algorithm for codes with N codewords. In fact, the NCP result even holds for a family of codes with a single code of each cardinality, and our hardness result therefore also applies to the preprocessing variant of the problem.

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. As in those works, we also prove weaker hardness results for approximate versions of these problems (showing that there is no N^{o(1)}-time algorithm in this case).

Based on joint work with Vinod Vaikuntanathan that will appear at FOCS 2019.