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

zbMATH Open1297.94128MaRDI QIDQ2921702FDOQ2921702

Authors: Alexander Vardy, Venkatesan Guruswami 

Publication date: 13 October 2014

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

Mathematics Subject Classification ID

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

Cited In (11)

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

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)