Computing, IT & AI

List decoding of Reed-Solomon codes

1997-1999 CEMadhu Sudan and Venkatesan GuruswamiGuruswami & Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes (1999)Diaspora (work abroad)

1997

Decoding that recovers data from far more errors than was thought possible, by returning a short list of candidates.

Dated: 1997–1999
As scholars put it: 1997-1999 CE
Originator: Madhu Sudan and Venkatesan Guruswami
Source text: Guruswami & Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes (1999)
Region: Diaspora (work abroad)
Discipline: Computing, IT & AI
Evidence: Documented
Confidence: High
Verification: Verified-web

Background

Classical decoders give up beyond half the minimum distance of a code. Madhu Sudan (1997), and then Sudan with his student Venkatesan Guruswami, an IIT Madras graduate (1999), gave efficient algorithms that list-decode Reed-Solomon codes well beyond that limit.

Significance

Reopened a question considered settled since the 1950s and connected coding theory with complexity and pseudorandomness. Sudan received the Nevanlinna Prize in 2002.

Path to modern innovation

Reed-Solomon codes protect QR codes, storage and deep-space links.

Global impact

Stronger error correction and new tools in complexity theory.

References

4Improved decoding of Reed-Solomon and algebraic-geometry codes V. Guruswami and M. Sudan, 1999