Venkatesan Guruswami and Atri Rudra
Limits to list decoding Reed-Solomon codes
Abstract :
Starting with the seminal work of Shannon in 1948,
much progress was made in the construction of good error-correcting
codes with efficient
decoding algorithms for the
probabilistic noise model.
However, in the adversarial noise model,
all
decoding algorithms were constrained by the necessity to output a unique codeword. This
in turn implies that the number of errors is upper bounded by half
the minimum distance of the code.
List-decoding circumvents this issue by allowing
the decoding algorithm to output a list of codewords with the guarantee that
the list contains the transmitted codeword.
Note that such a tradeoff is necessary as insisting on decoding with
unique codeword makes it impossible to correct errors more than half
the minimum distance.
While
this notion was introduced in the 1950's, efficient list decoding algorithms
remained elusive until the work of Sudan in the mid 1990's.
Guruswami and Sudan devised
a polynomial time list decoding algorithm for an important and well-studied code called the Reed-Solomon (RS) code.
Their algorithm satisfies a certain trade-off with respect to the
number of errors it can handle --- we call this trade-off the
Johnson bound. Subsequent works have
achieved better tradeoffs (see for example our work in STOC06) for other
codes. However, Reed-Solomon codes are important codes in their own
right and it will be nice to pin point the correct tradeoff achievable
for such codes.
In this work,
we show that for a generalization of the list
decoding of RS code, called polynomial reconstruction,
no algorithm can tolerate more error
than the Johnson bound. In particular this shows that a RS list decoding
algorithm that solves the general problem of polynomial reconstruction
(like the Guruswami-Sudan algorithm) cannot go beyond the square root bound.
Versions