Continuing the study of error detecting and correcting codes based on Guruswami’s list decoding [1], this paper’s idea is to obtain, as result of decoding, a small list of candidate messages that will, of course, include the correct message. The algorithms constructed make it possible to raise the decoding capacity for the worst-case model (Hamming model), bridging the gap--nearly eliminating it for codes over large alphabets--between the performance of this model and the probabilistic noise model (Shannon model). In summary, the paper introduces and motivates the problem of list decoding and discusses the central algorithmic results of the subject, culminating with the recent results on achieving “list decoding capacity.”

Considering the paper is 88 pages, it can be considered a small book. After the first two introductory chapters of definitions and terminology, chapter 3 lists combinatorial results concerning list-decodable codes, and studies the relation between the list decodability of a code and its other basic parameters such as minimum (Hamming) distance and rate (the amount of nonredundant information per bit of codeword).

Chapter 4 describes a list-decoding algorithm for Reed-Solomon (RS) codes that can be decoded up to the Johnson radius; namely, for a RS code with the rate R, the fraction of errors that can be corrected is 1-sqrt(R). Chapter 5 concludes the first part with a brief discussion on algorithmic results for graph-based list-decodable codes. This chapter is fairly informal--for details, the readers will have to seek other references.

In chapter 6, folded RS codes (RS codes considered as codes over a larger alphabet) are introduced. A decoding algorithm for folded RS codes is presented. It uses multivariate interpolation, plus some other algebraic ideas concerning finite fields, leading to an approach for list-decoding capacity. Folded RS codes are defined over a polynomially large alphabet. In chapter 7, some techniques that decrease the alphabet size (to a constant independent of the block length) are presented and analyzed. Chapter 8 is dedicated to conclusions and open questions for future follow-up.

In conclusion, the most important results contained in this paper concern RS codes ability to: improve list size of capacity-achieving codes, and achieve capacity over small alphabets.