PIMS - SFU Distinguished Discrete Math talk: Joris van der Hoeven

This is the second of a two-part talk. In talk one, I will review various well-known algorithms for integer multiplication, such as schoolbook multiplication, Karatsuba multiplication, FFT multiplication, and the Schoenhage-Strassen algorithm. The talk will also be an occasion to survey various basic techniques that will be useful for the second talk.

In this second talk, I will present a recent algorithm for multiplying two n-bit integers in time O(n log n).

Speaker Abstract:

Joris VAN DER HOEVEN is a Dutch computer scientist and mathematician, who received his PhD in 1997 at École polytechnique and his habilitation in 2008 at University Paris-Sud. He is currently director of research at CNRS and École polytechnique, as well as visiting professor at SFU. His main topics of interest are asymptotic algebra, fast arithmetic, and computer algebra. Joris VAN DER HOEVEN is the author of two books,more than 100 research papers, and the main developer of the scientific text editor GNUTEXMACS (http://www.texmacs.org). Together with Lou VAN DENDRIES and Matthias ASCHENBRENNER, he received the KARP prize in 2018 for the book Asymptotic Differential Algebra and Model Theory of Transseries. They were also invited speakers at ICM2018. In 2019, David HARVEY and Joris VAN DER HOEVEN proved that two n-bit integers can be multiplied in time O(n log n), thereby solving an important problem in theoretical computer science.