Faster List Decoding of AG Codes

Abstract

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{\ell }^{\ddot{I}‰-1}\hat{I}{¼}^{\ddot{I}‰-1}(n+g)+{\ell }^{\ddot{I}}‰\hat{I}{¼}^{\ddot{I}}‰)$ 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, $\ell$ is the designed list size and $\hat{I}¼$ is the smallest positive element in the Weierstrass semigroup of some chosen place.

13 pages (two-column format), 2 algorithms