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

Faster List Decoding of AG Codes

Abstract

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)

Licence

Attribution - NonCommercial - NoDerivatives

Identifiers

  • HAL Id : hal-04069465 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More