Exciting preprint on decoding now on arXiv

A preprint on fast decoding of AG codes is now available on arXiv here. It was written by Peter Beelen, Johan Rosenkilde, and Grigory Solomatov. In the preprint, it is explained how to decode any AG code fast. In fact, the obtained decoding complexity is at least as fast as any previously known algorithm even when specified to particular AG codes such as the highly studied one-point Hermitian codes. It should be said however, that for Reed-Solomon codes, which can be viewed as AG codes as well, there exists a slightly faster decoding algorithm.

The result in the preprint may well become the bench mark for any future work on decoding AG codes. They also appeared as a chapter in the recent PhD thesis of Grigory Solomatov. Needless to say that we are very excited by the obtained results!

Update (November 2022): the paper has appeared in the highly esteemed journal IEEE Transactions on Information Theory!

The article  “On the constant D(q) defined by Homma” by the algebra group members Peter Beelen, Maria Montanucci, and Lara Vicino has been accepted for publication in the Proceedings of the 18th Conference on Arithmetic, Geometry, Cryptography, and Coding Theory in the AMS book series Contemporary Mathematics (CONM). In this article, we investigate the asymptotic behaviour of the number of points on an algebraic curve defined over a finite field in relation to its degree. A preprint of this article can be found here.

Today, Grigory defended his Ph.D. thesis successfully! After giving an excellent presentation on his work, he answered various questions from his opponents. During his Ph.D. Grigory obtained various results on computational aspects of algebraic geometry (AG) codes, including results on encoding and decoding such codes. The results include decoding any AG code very efficiently, matching and very often improving preexisting decoders.

We would like to acknowledge the support from The Danish Council for Independent Research (DFF-FNU) for the project Correcting on a Curve, Grant No. 8021-00030B. Their support made Grigory’s Ph.D. project and the obtained results a reality.

Congratulations to Grigory with obtaining his Ph.D.-degree!

Yesterday, Grigory Solomatov handed in his PhD thesis “Computational Aspects of Algebraic Geometry Codes”. We would like to congratulate Grigory with this! His PhD defense is planned to take place on the 16th of December.

Grigory’s PhD was financed by the DFF-FNU project “Correcting on a curve”. Grigory will stick around a bit longer, since it was possible to hire him as a research assistant till the end of the year.

The paper “Point-line incidence on Grassmannians and majority logic decoding of Grassmann codes” by Peter and Prasant Singh appeared online in the journal Finite Fields and Their Applications. In this paper Peter and Prasant, a former postdoc of the algebra group, explain how to use the subtle structure of lines on Grassmannians to correct errors using Grassmann codes with an old technique called majority logic decoding. The result is a fast decoding algorithm for Grassmann codes.

Peter and Maria participated from 31st May – 4th June 2021 in the biannual conference AGCT, where researchers from all over the world discuss algebraic geometry/number theory and their applications. This year the conference was held online, due to the covid19 situation. Peter gave a talk “On a conjecture by Sørensen” on Thurday, 3rd June, in which he explained his work with Mrinmoy Datta and Masaaki Homma on the maximal number of intersection points on a non-degenerate Hermitian variety and a surface of degree d. This work has appeared recently in Proc. Amer. Math. Soc. 149 (2021), no. 4, 1431–1441. A preprint is available here.

Peter and Maria participated in the online conference “Curves over Finite Fields”, which took place 24-28 May. The conference was originally planned to take place in Benasque, but was held online, due to the covid19 situation.

Peter was an invited plenary speaker and gave two talks: “Asymptotic results: an overview” and “Asymptotic results: what is next?”. In the first talk, he gave an overview of results on asymptotically families of curves over a finite field with many rational points. In the second talk, several open problems and very recent developments were explained.

Maria was an invited semi-plenary speaker and gave the talk “On the automorphism group of algebraic curves in positive characteristic”. In the talk, she gave an overview on the latest developments on relation between various invariants of algebraic curves, such as p-rank, genus, and their automorphism groups.

We are happy to say that the given talks were well received!

Peter has been one of the lectures in an international workshop organized by leading technical universities in India: IIT Bombay, IIT Jammu and SGGS-IET. The online event took place March 8-12 and had many participants from all over the world. Peter gave two lectures on the decoding of Reed-Solomon codes. Slides of his and other talks are available here.

In the issue of this month of the prestigious journal IEEE Transactions on Information Theory, you can find the article “Fast Encoding of AG Codes over C_ab Curves” by Peter, Johan, and Grigory. In this article it is explained how to convert a message into a codeword (encoding) as well as the reverse process (unencoding) fast for a significant class of algebraic geometry codes. A preprint is available here.

Starting the first of March 2021 Johan left DTU for a job at GitHub as a Research Engineer. The algebra group would like to thank him for his input, energy and enthusiasm throughout the years. Best of luck with your new job!