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 ) Î F2, 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. 17 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 Xi Yj 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. 10
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.
Y
L (X, Y) = Y − X
2
4
3
2
1
− 6 − 4 − 2
− 5 − 3 − 1
246
135
− 1
− 2
− 3
− 4
X
E(X, Y) = Y 2/16 + X 2/49 − 1
L (X, Y) = Y + X
1
Q(X, Y) = L (X, Y) • L (X, Y) • E(X, Y)
12
n = 14, k = 2, e = 9