  We present algorithms performing sparse univariate polynomial interpolation
with errors in the evaluations of the polynomial. Based on the initial work by
Comer, Kaltofen and Pernet [Proc. ISSAC 2012], we define the sparse polynomial
interpolation codes and state that their minimal distance is precisely the
length divided by twice the sparsity. At ISSAC 2012, we have given a decoding
algorithm for as much as half the minimal distance and a list decoding
algorithm up to the minimal distance. Our new polynomial-time list decoding
algorithm uses sub-sequences of the received evaluations indexed by a linear
progression, allowing the decoding for a larger radius, that is, more errors in
the evaluations while returning a list of candidate sparse polynomials. We
quantify this improvement for all typically small values of number of terms and
number of errors, and provide a worst case asymptotic analysis of this
improvement. For instance, for sparsity T = 5 with up to 10 errors we can list
decode in polynomial-time from 74 values of the polynomial with unknown terms,
whereas our earlier algorithm required 2T (E + 1) = 110 evaluations. We then
propose two variations of these codes in characteristic zero, where appropriate
choices of values for the variable yield a much larger minimal distance: the
length minus twice the sparsity.
