in fact two parts to the above question. First, the code should be such that the identity of the message is uniquely (or near uniquely) pinned down based on the noisy version of its encoding. Second, we need an efficient procedure to recover the message based on the corrupted codeword, with runtime bounded by a hopefully small polynomial in the block length n. Brute-force approaches such as searching through all codewords require time exponential in n, and are computationally prohibitive. The main message of this article is that a variant of the widely deployed Reed–Solomon codes can in fact be error-corrected efficiently, even as the fraction of errors approaches the absolute 1 − R limit.

We stress that in the above question, the noise model is a worst-case one, where the channel is modeled as an adver-sary/jammer that can corrupt the codeword in an arbitrary manner, subject only to a limit on the total number of errors. No assumptions are made on how the errors are distributed. The worst-case model was put forth in Hamming’s influential paper. ¹² An alternate approach, pioneered by Shannon in his seminal work, ¹⁶ is to model the noisy channel as a stochastic process whose behavior is governed by a precisely known probability law. A simple example is the binary symmetric channel (BSC ) where each bit transmitted gets

r
flipped with a probability r, independent of all other bits.
For every such channel, Shannon exactly characterized the
largest rate at which reliable communication is possible.

We note that obtaining algorithmic results is more difficult in worst-case noise model. In fact, traditionally it was believed that codes designed for worst-case noise faced a limit of ( 1 − R)/2 fraction of errors, which is factor 2 off from the information-theoretic limit of a ( 1 − R) fraction of errors. In attempting to correct e > (n − k)/2 errors, we face a problem: there may be more than one codeword within Hamming distance e from the received word. In any code mapping k symbols to n symbols, there must be two codewords at distance (n − k + 1) or less. If one of these codewords is transmitted and gets distorted by errors to halfway between the two codewords, unambiguous recovery of the original message becomes infeasible. This suggests that beyond a fraction ( 1 − R)/2 of worst-case errors, the original message is unrecoverable. This was indeed the conventional wisdom in coding theory till the 1990s.

A natural strategy, in the event of multiple close-by codewords, would be to allow the decoder to output a list of codewords. This model is called list decoding. It was introduced in the late 1950s by Elias² and Wozencraft, ¹⁹ and revived with an algorithmic focus for a cryptographic application by Goldreich and Levin. ⁴ Further, it turns out that the bad case above is rather pathological—for typical patterns of e errors, for e much bigger than (n − k)/2, the original codeword will be the only codeword within distance e. Thus, list decoding in addition to handling the bad error patterns for “unique”

b

decoding, also allows us to uniquely recover the transmitted codeword for most error patterns.

It is interesting to note that even though the list decoding problem has a long history in the coding theory world,^a a

large share of the algorithmic progress in list decoding has happened in the theoretical computer science community. One of the reasons for this happy coincidence is that list decoding has found numerous applications in cryptography and computational complexity theory (e.g., see the discussion on randomness extractors in Section 5).

In particular, in the last decade, the subject of list decoding has witnessed a lot of activity, culminating in algorithms that correct close to the information-theoretically optimal 1 − R fraction of errors with rate R. The purpose of this article is to discuss this recent body of results which deliver the full promise of codes against worst-case errors. We begin in Section 2 by describing a popular family of codes and a few decoding algorithms for it.

2. ReeD–soLomon coDes

In 1960, Irving Reed and Gustave Solomon described a construction of error-correcting codes, which are called Reed–Solomon codes after them, based on polynomials over finite fields.^b Almost 50 years after their invention, Reed–Solomon codes (henceforth, RS codes) remain ubiquitous today in diverse applications ranging from magnetic recording to UPS bar codes to satellite communications. To describe the simple and elegant idea behind RS codes, imagine Alice wishes to communicate a pair of numbers (a, b) to Bob. We can think of (a, b) as specifying a line in the plane (with X, Y axes) with equation Y = aX + b. Clearly, to specify the line, it suffices to communicate just two points on the line. To guard against errors, Alice can oversample this line and send more points to Bob, so that even if a few points are distorted by errors, the collection of points resembles the original line more closely than any other line (Figure 1). Thus, Bob can hope to recover the correct line, and in particular (a, b).

To encode longer messages consisting of k symbols via an RS code, one thinks of these as the coefficients of a polynomial f (X) of degree k − 1 in a natural way, and encodes the message as n > k points from the curve Y − f (X) = 0.

figure 1: oversampling from a line Y = aX + b to tolerate errors, which occur at X = 3 and 5.

Y

X

1

2

3

4

5

6

7

a

The problem was introduced about 50 years ago and the main combinatorial limitations of list decoding were established in the 1970s and 1980s.

b

For this article, readers not conversant with fields can think of a finite field as {0, 1, . . . , p− 1) for a prime p with addition and multiplication operations defined modulo p.