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 Õ(s²ℓ^ω−1μ^ω−1(n + g) + ℓ^ωμ^ω) 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, ℓ is the designed list size and μ is the smallest positive element in the Weierstrass semigroup of some chosen place.