Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
From MaRDI portal
Publication:3546964
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
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