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

Simple item page
dc.creatorGuruswami, Venkatesan
dc.creatorVardy, Alexander
dc.date2004-05-04
dc.date.accessioned2026-07-07T08:17:41Z
dc.date.available2026-07-07T08:17:41Z
dc.descriptionMaximum-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.
dc.description16 pages, no figures
dc.identifierhttps://arxiv.org/abs/cs/0405005
dc.identifierhttp://arxiv.org/abs/cs/0405005
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/134176
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectInformation Theory
dc.subjectE.4; F.1.3; F.2.1
dc.titleMaximum-likelihood decoding of Reed-Solomon Codes is NP-hard
dc.typetext

Files

Collections

arXiv