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.