Faster List Decoding of AG Codes - Sorbonne Université Access content directly
Preprints, Working Papers, ... Year : 2023

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 $\tilde{O}(s^2\ell^{\omega-1}\mu^{\omega-1}(n+g) + \ell^\omega \mu^\omega)$ 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 $\mu$ is the smallest positive element in the Weierstrass semigroup of some chosen place.
Fichier principal
Vignette du fichier
ag-decoding-faster.pdf (639.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Licence : CC BY NC ND - Attribution - NonCommercial - NoDerivatives

Dates and versions

hal-04069465 , version 1 (14-04-2023)


Attribution - NonCommercial - NoDerivatives


  • HAL Id : hal-04069465 , version 1


Peter Beelen, Vincent Neiger. Faster List Decoding of AG Codes. 2023. ⟨hal-04069465⟩
26 View
31 Download


Gmail Facebook X LinkedIn More