We present a randomized algorithm which takes as input n distinct points {(xi, yi)}ni=1 from F x F (where F is a field) and integer parameters t and d and returns a list of all univariate polynomials f over F in the variable x of degree at which most d which agree with the given set of points in at least t places (i.e., yi = f(xi), for at least t values of i), provided t = Omega(nd). The running time is bounded by a polynomial in n. This immediately provides a maximum likelihood decoding algorithm for Reed Solomon Codes, which works in a setting with a larger number of errors than any previously known algorithm. To the best of our knowledge, this is the first efficient (i.e., polynomial time bounded) algorithm which provides error recovery capability beyond the error-correction bound of a code for any efficient (i.e., constant or even polynomial rate) code.

By:* Madhu Sudan *

Published in: Journal of Complexity, volume 13, (no 1), pages 180-93 in 1997

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .