Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard

DOI10.1109/TIT.2005.850102zbMath1310.94210arXivcs/0405005MaRDI QIDQ3546964

Alexander Vardy, Venkatesan Guruswami

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0405005

Mathematics Subject Classification ID

94B27: Geometric methods (including applications of algebraic geometry) applied to coding theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

94B35: Decoding

Related Items

NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem, Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius, On the error distance of extended Reed-Solomon codes, Key masking using biometry, Power error locating pairs, Improvements on the Johnson bound for Reed-Solomon codes, On error distance of Reed-Solomon codes, On deep holes of Gabidulin codes, Computing sparse multiples of polynomials, On deep holes of standard Reed-Solomon codes, On deep holes of generalized Reed-Solomon codes, Some results on deep holes of generalized projective Reed-Solomon codes, On Reed-Solomon codes, ECC\(^2\): error correcting code and elliptic curve based cryptosystem, On the equivalence of two post-quantum cryptographic families, Basics of Secrecy Coding