# Fast Multivariate Multipoint Evaluation Over All Finite Fields

**Authors:** Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans  
**arXiv:** [2205.00342](https://arxiv.org/abs/2205.00342)  
**Date:** 2022-04-30  
**Summary page:** https://www.summarizepaper.com/en/paper/2205.00342v1/

## Key points

- The authors present a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$.
- The algorithm outputs evaluations of an $m$-variate polynomial of degree less than $d$ in each variable at $N$ points in time $(d^m+N)^{1+o(1)}\cdot\poly(m, d, \log|\mathbb{F}|)$.
- This result builds on previous works by Kedlaya and Umans (FOCS 2008, SICOMP 2011) and Bhargava et al. (STOC 2022).
- The authors remove the constraint on the number of variables over all finite fields.
- The algorithm presented combines ideas from three previously known algorithms for multivariate multipoint evaluation and utilizes Bombieri-Vinogradov Theorem from analytic number theory.
- A second algorithm is also presented that is completely elementary but requires a mild assumption about the field size being bounded by an exponential-tower in $d$ of bounded height.
- Overall, this work provides a significant advancement in the field of multivariate multipoint evaluation by presenting algorithms that work over all finite fields and removing constraints on the number of variables.

## Summary

In this work, Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar and Chris Umans present a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of degree less than $d$ in each variable at $N$ points in time $(d^m+N)^{1+o(1)}\cdot\poly(m, d, \log|\mathbb{F}|)$. This result builds on previous works by Kedlaya and Umans (FOCS 2008, SICOMP 2011), who achieved the same time complexity when the number of variables $m$ is at most $d^{o(1)}$, but left the problem of removing this condition as an open question. A recent work by Bhargava et al. (STOC 2022) answered this question when the underlying field is not \emph{too} large and has characteristic less than $d^{o(1)}$. In this work, the authors remove this constraint on the number of variables over all finite fields. The algorithm presented relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation: those of Kedlaya and Umans; Bj\"orklund, Kaski and Williams (IPEC 2017, Algorithmica 2019); and Bhargava et al. Additionally, it utilizes a result from analytic number theory about the distribution of primes in an arithmetic progression known as Bombieri-Vinogradov Theorem. The authors also present a second algorithm for multivariate multipoint evaluation that is completely elementary and avoids the use of the Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in $d$ of bounded \textit{height}. Overall, this work provides a significant advancement in the field of multivariate multipoint evaluation by presenting algorithms that work over all finite fields and removing constraints on the number of variables.