Faster List Decoding of AG Codes
Peter Beelen, Vincent Neiger · IEEE Transactions on Information Theory · 2025
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 {\mathcal {O}} (s^{2}\ell ^{\omega -1}\mu ^{\omega -1}(n+g) + \ell ^{\omega } \mu ^{\omega })$operations in the underlying finite field, wherenis the code length,gis the genus of the function field used to construct the code,sis the multiplicity parameter,$\ell $is the designed list size and$\mu $is the smallest positive element in the Weierstrass semigroup of some chosen place.