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

DOI10.1109/TIT.2005.850102MaRDI QIDQ3546964zbMATH OpenFDO

Authors 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

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

Abstract: Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum- likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. In this paper, we prove that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of Bruck and Naor.

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.)
• The “Art of Trellis Decoding” Is NP-Hard
• Decoding of Reed Solomon codes beyond the error-correction bound
• Complexity of Decoding Positive-Rate Reed-Solomon Codes
• The decoding of extended Reed-Solomon codes
• Fast maximum likelihood decoding of Reed-Muller codes
• Fast maximum likelihood decoding of Reed-Muller codes
• A Decoding Approach to Reed–Solomon Codes from Their Definition

Cited in

(24)

• 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
• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• On the error distance of extended Reed-Solomon codes
• Basics of secrecy coding
• The hardness of decoding linear codes with preprocessing
• Complexity of Decoding Positive-Rate Reed-Solomon Codes
• On the Hardness of Decoding the Gale–Berlekamp Code
• Hard Problems of Algebraic Geometry Codes
• NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
• Randomized decoding of Gabidulin codes beyond the unique decoding radius
• Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH
• Deep holes of twisted Reed-Solomon codes
• Smooth symmetric systems over a finite field and applications
• Key masking using biometry
• Power error locating pairs

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 Q3546964)