Zeyu Guo: Fast Multivariate Multipoint Evaluation over All Finite Fields

(Zoom password: 728726)

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. The most straightforward algorithm is simply evaluating the polynomial at each evaluation point, which has quadratic time complexity. It is a fundamental question to design better or even almost linear time algorithms for this problem.

Over finite fields, Kedlaya and Umans (2008) first gave an almost linear time algorithm for this problem when the number of variables is sub-polynomial in d, where d is the individual degree bound for the input polynomial. A recent work by Bhargava, Ghosh, Kumar, and Mohapatra (2022) gave another almost linear time algorithm for sufficiently large d when the underlying finite field is not too large and has a small characteristic.

In this talk, I will present a new algorithm for this problem that runs in almost linear time for sufficiently large d, regardless of the number of variables and the characteristic of the finite field. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski, and Williams (2017), and that of Bhargava, Ghosh, Kumar, and Mohapatra, together with a result in analytic number theory about the distribution of primes in an arithmetic progression.

This is joint work with Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chris Umans.