Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

MaRDI QIDQ2921702zbMATH OpenFDO

Authors Alexander Vardy, Venkatesan Guruswami

Publication date 13 October 2014

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)

Recommendations

• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
• On the complexity of decoding Reed-Solomon codes (Corresp.)
• Decoding of Reed Solomon codes beyond the error-correction bound
• Complexity of Decoding Positive-Rate Reed-Solomon Codes
• The “Art of Trellis Decoding” Is NP-Hard
• Fast maximum likelihood decoding of Reed-Muller codes
• Fast maximum likelihood decoding of Reed-Muller codes
• The decoding of extended Reed-Solomon codes
• Complexity of Decoding Positive-Rate Primitive Reed–Solomon Codes

Cited in

(11)

• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• Deep holes in Reed-Solomon codes based on Dickson polynomials
• Complexity of Decoding Positive-Rate Reed-Solomon Codes
• On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability
• On the hardnesses of several quantum decoding problems
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Hard Problems of Algebraic Geometry Codes
• NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
• On the Hardness of Decoding the Gale–Berlekamp Code
• Algorithms for modular counting of roots of multivariate polynomials
• The hardness of decoding linear codes with preprocessing

This page was built for publication: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921702)