Communications - March 2009

and be of the form P(X, Y) A(X) for some nonzero (possibly constant) polynomial A(X). The intuitive reason is that since there are so few errors in the data compared to the curve Y − f (X) = 0, the curve P(X, Y) = 0 is the most economical way to fit all the data points. The formal proof proceeds by considering the polynomial , and arguing it must be identically zero since (i) it has at least (n + k)/2 roots (namely all a ’s for which f (a ) = y ) and (ii) it has degree less than i ii

(n + k)/2 (by design of Q(X, Y) ). Thus, Q(X, Y) also has Y − f (X) as a factor, and we can recover f (X) by factoring Q(X, Y). (The actual task here is easier than general bivariate polynomial factorization, and admits near-linear time algorithms.)

2. 2. List decoding Reed–solomon codes

We now turn to list decoding of Reed–Solomon codes. The
setup is as before: given n points (a , y ) Î F², find polynomi-
ii
als f (X) of degree less than k such that f (a ) ≠ y for at most e
ii
locations i. The difference is that now e >> (n − k)/2, and so
there may be more than one such polynomial f (X) that the
decoder needs to output.

Before delving into the algorithms, we pause to consider how large a number of errors e one can target to correct. Clearly, we need the guarantee there will be only a few (say, at most polynomially many in n) solution polynomials f (X) or else there is no hope for the decoder to output all of them in polynomial time. Using the fact that encodings of any two polynomials differ in more than (n − k) locations, it can be shown (via the so-called “Johnson bound”) that for the number of solutions (called the list size) is guaranteed to be polynomially small. Whether one can prove a polynomial list size bound for certain RS codes for even larger e remains a key open question.

We now describe the idea underlying Sudan’s breakthrough algorithm for list decoding RS codes. ¹⁷ Recall that we want to solve a noisy curve fitting problem, and output all curves Y − f (X) = 0 with deg( f ) < k that pass through n − e or more of the n points (a , y ). For e ≤ (n − k)/2, the Berlekamp–

ii

Welch algorithm interpolated a bivariate polynomial Q(X, Y) of a very specific format through all the n points. Sudan’s idea for e > (n − k)/2 was to interpolate/fit a general nonzero curve Q(X, Y) = 0 of just high enough “degree” (so that its existence is guaranteed) through all the n points. Fitting such a curve can be done efficiently by solving a system of linear equations to determine the coefficients of Q(X, Y).

For the Berlekamp– Welch algorithm, arguing that Y − f (X) was a factor of Q(X, Y) followed from the very special structure of Q(X, Y). In the list decoding case, Sudan exploited special properties of intersections of curves of the form Y − f (X) with any interpolated bivariate polynomial Q(X, Y) with appropriate degree constraints. Informally, Sudan’s idea is that given the strong degree constraint on Q(X, Y ), every curve Y − f (X) = 0 with deg( f ) < k that picks up at least n − e of points must be “used” by the interpolated curve in meeting the requirement to pass through all n points. As an example, in Figure 3, the goal is to find all lines (i.e., we have k = 2) that pass through all but e = 9 of the n = 14 input points (there are two such lines, marked in the figure as L (X, Y ) and

1

L (X, Y ) ). There are enough degrees of freedom in the equa-

2 tion of a degree 4 curve so that one can fit a degree 4 curve

90 communications of the acm | march 2009 | Vol. 52 | no. 3

through any set of 14 points. The figure illustrates one such curve, which is the product of the two lines with an “ellipse” E(X, Y ). (Note that the total degree of Q(X, Y ) is 4.) Further, we see that the two relevant lines pop out as factors. This is not a coincidence, and every degree 4 curve passing through the 14 points must have these two lines as factors. The reason: if a line is not a factor, then it can intersect a degree 4 curve in at most 4 points. Since each of these lines intersects any interpolated curve in at least 5 points, it must be a factor.

More formally, the “degree” measure of the interpolated polynomial Q(X, Y ) will be the ( 1, k − 1)-degree, which is defined as the maximum of i + (k − 1) j over all monomials XⁱY^j that occur with a nonzero coefficient in Q(X, Y). Let D denote the

( 1, k − 1) degree of Q(X, Y). Generalizing the above argument for lines, if a curve Y − f (X) = 0 with deg( f ) < k passes through more than D points, then Y − f (X) must be a factor of Q(X, Y). With a counting argument, one can show that a ( 1, k − 1)-degree D of suffices to fit a nonzero curve. Together, this leads to an algorithm that can correct errors, or a fraction of errors as a function of the rate R.

For low rates, this algorithm enables recovery even in settings when noise overwhelms correct data, and close to 100% of the symbols may be in error. This feature sets the stage for several powerful applications in cryptography and complexity theory. However, the algorithm does not give any improvement over the ( 1 − R)/2 error fraction corrected by traditional algorithms for rates > 1/3, and also falls short of the radius suggested by the combinatorial bounds.

We now turn to the improved algorithm correcting a fraction of errors due to Guruswami and Sudan. ¹⁰The key new idea is to insist that the interpolated polynomial Q(X, Y ) has multiple zeroes at each of the n points. To explain this, we attempt a high-level geometric description. Consider the example in Figure 4 with n = 10 points, the goal being to output all lines that pass through at least n − e = 4 points. This example cannot be solved by Sudan’s algorithm. Indeed, since there are five solution lines, if they are all factors of some interpolated curve, the curve must have degree at least 5. However, there is no guarantee that an arbitrary degree 5 curve through the points must have every line passing through 4 of the points as a factor (the line has to pass

figure 3: illustration of list decoding of Rs code that evaluates lines over the points − 7, − 5, − 4, . . . , 4, 5, 6, 7. the two lines are recovered as factors of a degree 4 interpolated curve through all the points.