Guruswami and several collaborators have developed the idea of list decoding of linear codes, focusing on folded Reed-Solomon codes. “Folded” means that one regards a sequence of n symbols, from the alphabet Σ, as a single symbol in the alphabet Σⁿ. In list decoding, the decoding algorithm outputs a list of codewords, rather than a single codeword. This list often consists of a single entry, due to the geometry of Hamming balls. Guruswami’s long introductory article [1] has already been reviewed in Computing Reviews.

Here, Guruswami presents an abstract version of the list-decoding algorithm, showing how it derives from Artin automorphisms of cyclotomic function fields.

A reader familiar with the basic theory of algebraic geometry codes can follow the reasoning, although some of the proofs only appear in the online version of the paper. A reader with a strong background in number theory should find it easy going, but may need to refer to the author’s other paper [1] for coding theory background. The author pays close attention to complexity issues, but does not address implementation.