Title: Fast list decoding of algebraic geometry codes
Abstract: In this talk, we present an efficient list decoding algorithm
for algebraic geometry (AG) codes. They are a natural generalization
of Reed-Solomon codes and include some of the best codes in terms
of robustness to errors. The proposed decoder follows the Guruswami-Sudan
paradigm and is the fastest of its kind, generalizing the decoder for one-point
Hermitian codes by J. Rosenkilde and P. Beelen to arbitrary AG codes.
In this fully general setting, our decoder achieves the complexity
$\widetilde{\mathcal{O}}(s \ell^{\omega}\mu^{\omega – 1}(n+g))$, where $n$
is the code length, $g$ is the genus, $\ell$ is the list size, $s$ is the multiplicity
and $\mu$ is the smallest nonzero element of the Weierstrass semigroup at
some special place.
Joint work with J. Rosenkilde and P. Beelen.
Algorithmic Number Theory, Coding and Cryptography
