SETH-Hardness of Coding Problems

We show that assuming the strong exponential-time hypothesis (SETH), there are no non-trivial algorithms for the nearest codeword problem (NCP), the minimum distance problem (MDP), or the nearest codeword problem with preprocessing (NCPP) on linear codes over any finite field. More precisely, we show that there are no NCP, MDP, or NCPP algorithms running in time q (1-ε)n for any constant ε > 0 for codes with q n codewords. (In the case of NCPP, we assume non-uniform SETH.) We also show that there are no sub-exponential time algorithms for y-approximate versions of these problems for some constant -y > 1, under different versions of the exponential-time hypothesis.

Authors

• Noah Stephens-Davidowitz
• Vinod Vaikuntanathan

Keywords

• Lattices
• Linear codes
• Heuristic algorithms
• Approximation algorithms
• Generators
• Data preprocessing
• Coding Problem
• Algorithm For Problem
• Finite Field
• Linear Code
• Sufficiently Large
• Reduction In Time
• Heuristic Algorithm
• Targeting Vector
• System Of Linear Equations
• Generator Matrix
• Null Vector
• Abuse Of Notation
• Sentence Condition
• Prime Power
• Alphabet Size
• Input Instance
• Hamming Weight
• Nonzero Solution
• Reed-Solomon Codes
• Coding problems, fine-grained hardness, SETH, linear codes