| Session: | 1.1.8 - List Decoding of Codes |
| Session Time: | Monday, July 10, 09:40 - 11:00 |
| Paper Time: | Monday, July 10, 10:00 - 10:20 |
| Title: |
Improved Hermite multivariable polynomial interpolation |
| Authors: |
Philippe Gaborit; University of Limoges | | |
| | Olivier Ruatta; University of Limoges | | |
| Abstract: |
In this paper we give an algorithm with complexity $\mathcal{O}\left({\mu}^2\right)$ to solve Hermite multivariable 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$ with multiplicity $m$ on each point, it permits to obtain a complexity in $\mathcal{O}\left(n^2m^4\right)$ better than previously known complexity in $\mathcal{O}\left(n^2m^5\right)$. 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 $r$ the general complexity of the algorithm is $\mathcal{O}\left(n^2m^{2M}\right)$. |
