Faster List Decoding of AG Codes

In this article, we present a fast algorithm performing an instance of the Guruswami-Sudan list decoder for algebraic geometry codes. We show that any such code can be decoded in $\tilde{O}(s^2{\mathrm{\ell }}^{\omega -1}{\mu }^{\omega -1}(n+g)+{\mathrm{\ell }}^{\omega }{\mu }^{\omega })$ operations in the underlying finite field, where $n$ is the code length, $g$ is the genus of the function field used to construct the code, $s$ is the multiplicity parameter, $\mathrm{\ell }$ is the designed list size and $\mu$ is the smallest positive element in the Weierstrass semigroup of some chosen place.