List-Decoding of AG Codes Without Genus Penalty

In this paper we consider algebraic geometry (AG) codes: a class of codes constructed from algebraic codes (equivalently, using function fields) by Goppa. These codes can be list-decoded using the famous Guruswami-Sudan (GS) list-decoder, but the genus g of the used function field gives rise to negative term in the decoding radius, which we call the genus penalty. In this article, we present a GS-like list-decoding algorithm for arbitrary AG codes, which we call the inseparable GS list-decoder. Apart from the multiplicity parameter s and designed list size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell $ </tex-math></inline-formula>, common for the GS list-decoder, we introduce an inseparability exponent e. Choosing this exponent to be positive gives rise to a list-decoder for which the genus penalty is reduced with a factor <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1/p^{e}$ </tex-math></inline-formula> compared to the usual GS list-decoder. Here p is the characteristic. Our list-decoder can be executed in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tilde {\mathcal {O}} (s\ell ^{\omega }\mu ^{\omega -1}p^{e}(n+g))$ </tex-math></inline-formula> field operations, where n is the code length and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tilde {\mathcal {O}} $ </tex-math></inline-formula> means that logarithmic factors are ignored.