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

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.

16 pages, no figures

Cited by in corpus (9)

• Iterative Algebraic Soft-Decision List Decoding of Reed-Solomon Codes
• On deep holes of standard Reed-Solomon codes
• On deep holes of generalized Reed-Solomon codes
• Singularities of symmetric hypersurfaces and an application to Reed-Solomon codes
• On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes
• Bounds on the ML Decoding Error Probability of RS-Coded Modulation over AWGN Channels
• On the equivalence of two post-quantum cryptographic families
• Fast Witness Counting
• Distance Distribution to Received Words in Reed-Solomon Codes