Computational Aspects of Algebraic Geometry Codes

This thesis is dedicated to an investigation of various computational problems associated with algebraic geometry (AG) codes – a diverse class of error-correcting codes among which one finds those that are the most robust to errors. Our main contribution consists of a Guruswami-Sudan style list-decoding algorithm that works for any AG code while being more efficient in this fully general setting than any previously known method. This is achieved by extending an existing technique that relies on row-reduction of polynomial matrices to solve the same problem in a more restricted context of one-point Hermitian codes. We also consider “improved power decoding” – a completely different decoding paradigm that revolves around certain key equations. Our contribution here consists of formulating these equations for all AG codes, whereas previous work has focused on specific cases. This formulation allows us to show that power decoding likely can correct as many errors as Guruswami-Sudan decoding, which is consistent with our numerical simulations. Although our decoder uses linear algebra and is therefore computationally expensive, its conceptual framework suggests a way of making it as efficient as our main contribution. Besides decoding, we also investigate encoding of AG codes, albeit in a less general setting, which reduces the problem to that of multi-point evaluation of bivariate polynomials. This allows us to develop algorithms that are extremely efficient for important special cases such as one-point Hermitian codes. We then consider bivariate multi-point evaluation in a setting completely divorced from AG codes, where we contribute with novel and efficient algorithms that utilize precomputation.