Decoding Interleaved Gabidulin Codes using Alekhnovich's Algorithm

We prove that Alekhnovich’s algorithm can be used for row reduction of skew polynomial matrices. This yields an $O({\mathrm{\ell }}^3{n}^{(\omega +1)\mathrm{/}2}\log (n))$ decoding algorithm for $\mathrm{\ell }$-Interleaved Gabidulin codes of length $n$, where $\omega$ is the matrix multiplication exponent, improving in the exponent of $n$ compared to previous results.