Faster List Decoding of AG Codes

04/14/2023

∙

by   Peter Beelen, et al.

∙

0

∙

share

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^2ℓ^ω-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.