Improved Hermite multivariate polynomial interpolation

In this paper we give an algorithm with complexity O (mu(2)) to solve Hermite multivariate polynomial interpolation with mu conditions on its Hasse derivatives. In the case of bivariate interpolation used to perform list-decoding on Reed-Solomon of length n and dimension k with multiplicity m on each point, it permits to obtain a complexity in O (n(2)m(4)) which does not depend on the rate k/n and better than previously known complexity in O (n(2)m(5)(n/k)2/1). This algorithm can also be used for recent interpolation list-decoding with three and more variables. For interpolation on polynomial with n points and M variables with prescribed multiplication order m the general complexity of the algorithm is O (n(2)m(2M)).