Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard
<|reference_start|>Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard: 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.<|reference_end|>
@article{guruswami2004maximum-likelihood,
    title={Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard},
    author={Venkatesan Guruswami and Alexander Vardy},
    journal={arXiv preprint arXiv:cs/0405005},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0405005},
    primaryClass={cs.CC cs.DM cs.IT math.IT}
}