We first present a new decoding algorithm for Reed-Solomon codes. The algorithm attempts to decode $M-1$ transmitted codewords together,using $M$-variate polynomial interpolation. It is shown that if the channel errors are synchronized – occur in the same positions in all the $M-1$ codewords – this algorithm can, in principle, correct up to n ( 1 - R^{(M-1)/M} ) errors in a Reed-Solomon code of length $n$ and rate $R$, which is significantly higher than the Guruswami-Sudan decoding radius. The first nontrivial case $M = 3$ is will be discussed in detail. For this case, we show how to achieve trivariate interpolation using a gen eralized version of Koetter's iterative algorithm. We then recover the transmitted polynomials $f(X)$ and $g(X)$ from the output of this algorithm. In contrast to the bivariate case, the recovery of $f(X)$ and $g(X)$ requires at least TWO polynomials that satisfy the interpolation constraints. In fact, our recovery method is based upon computing certain resultants of the elements of a Groebner basis for the ideal of ALL such polynomials. In order to achieve deterministic decoding in polynomial time, our algorithm gradually reduces its decoding radius until the number of codewords within a certain decoding region becomes polynomially bounded. Thus it decodes beyond the Guruswami-Sudan radius only with a certain (high) probability. However, recently, we have constructed a family of algebraic codes that are provably decodable beyond the Guruswami-Sudan radius in the WORST-CASE. The key idea is to combine multivariate interpolation decoding with a kind of “inverted” algebraic-geometric construction. That is, instead of evaluating certain functions at the rational points of a curve, we evaluate the rational points THEMSELVES, viewed as pairs of polynomials over a subfield, at certain elements of the subfield. The equation that defines the curve thus provides the second polynomial we need in the recovery process. (*joint work with Farzad Parvaresh (University of California San Diego))

Full presentation