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

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)

Related Items (16)

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

This page was built for publication: Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard