Generic interpolation polynomial for list decoding (Q661987)

In this article list decoding of one-point algebraic geometry codes is studied, given a nonsingular, absolutely irreducible projective curve defined over a finite field. A one-point algebraic geometry code is obtained by assigning to the functions of a Riemann-Roch space of the form \(L(rP)\), with \(P\) a rational point on the curve, codewords of the form \((f(P_1),\dots,f(P_n))\), with \(P_1,\dots,P_n\) other rational points on the curve. The list decoding of such codes can be done using the Guruswami-Sudan list decoding algorithm. In this algorithm an interpolation polynomial needs to be found. The interpolation polynomial \(Q\) depends on the received word \((r_1,\dots,r_n)\), since it is required to satisfy that it has \((P_i,r_i)\) as a zero, possibly with a certain multiplicity. All interpolation polynomials lie in a certain ideal and the interpolation polynomial needed in the list-decoding algorithm can be found using Gröbner basis techniques. In this paper results of Lee and O'Sullivan are extended to show how to find the interpolation polynomial needed for the list decoding of one-point algebraic geometry codes. Then a generic point of view is taken: since the interpolation polynomial depends on the received word \((r_1,\dots,r_n)\), one can try to find a generic interpolation polynomial by regarding \(r_1,\dots,r_n\) as variables. Specializing these variables in the generic interpolation polynomial to the actually received values, one can obtain the interpolation polynomial needed for the decoding. This approach is certainly of theoretical interest, though it is difficult to find an explicit generic interpolation polynomial if one wants to correct many errors. In the example given in the paper, the authors consider a \([q-1,q-3,3]\) Reed-Solomon code (meaning the underlying algebraic curve is the projective line). A generic interpolation polynomial is given assuming at most one error has occurred.