Guruswami V. Algorithmic Results in List Decoding

From the Foundations and Trends in Theoretical Computer Science series by NOWPress, 2006, -91 p.Error-correcting codes are used to cope with the corruption of data by noise during communication or storage. A code uses an encoding procedure that judiciously introduces redundancy into the data to produce an associated codeword. The redundancy built into the codewords enables one to decode the original data even from a somewhat distorted version of the codeword. The central trade-off in coding theory is the one between the data rate (amount of non-redundant information per bit of codeword) and the error rate (the fraction of symbols that could be corrupted while still enabling data recovery). The traditional decoding algorithms did as badly at correcting any error pattern as they would do for the worst possible error pattern. This severely limited the maximum fraction of errors those algorithms could tolerate. In turn, this was the source of a big hiatus between the error-correction performance known for probabilistic noise models (pioneered by Shannon) and what was thought to be the limit for the more powerful, worst-case noise models (suggested by Hamming).
In the last decade or so, there has been much algorithmic progress in coding theory that has bridged this gap (and in fact nearly eliminated it for codes over large alphabets). These developments rely on an error-recovery model called list decoding, wherein for the pathological error patterns, the decoder is permitted to output a small list of candidates that will include the original message. This book 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.Part I General LiteratureDefinitions and Terminology
Combinatorics of List Decoding
Decoding Reed–Solomon Codes
Graph-Based List-Decodable Codes
Part II Achieving List Decoding Capacity
Folded Reed–Solomon Codes
Achieving Capacity over Bounded Alphabets
Concluding Thoughts