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.
This is a very complicated topic that is hard to explain to a six-year-old. But basically, some really smart people made a new way of doing math with lots of numbers and variables. They figured out how to do it faster and better than before, which is really cool! They used ideas from other smart people who did similar things before. And now, they can do this kind of math with any type of number, not just some types like before. This will help other smart people solve even more complicated problems in the future!
Definitions
- Algorithm: A set of instructions for solving a problem or completing a task.
- Finite field: A type of mathematical structure where there are only a finite number of elements (numbers) that you can use.
- Polynomial: An expression consisting of variables and coefficients, involving addition, subtraction, and multiplication.
- Degree: The highest power (exponent) in a polynomial.
- Constraint: A limitation or restriction on something.
- Analytic number theory: A branch of mathematics that studies properties of numbers using methods from calculus and analysis.
An Overview of Multivariate Multipoint Evaluation
Multivariate multipoint evaluation is an important problem in computational algebra and number theory. It involves computing the evaluations of a multivariate polynomial at multiple points in a finite field. This problem has been studied extensively over the past few decades, with researchers developing algorithms to solve it more efficiently.
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$ was 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 was not \emph{too} large and had characteristic less than $d^{o(1)}$. In this work, however, the authors remove this constraint on the number of variables over all finite fields.
The Algorithm Presented
The algorithm presented relies on a non-trivial combination of ideas from three 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 using Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in $d$ with bounded \textit{height}.
Conclusion
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.
Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists 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}|) \] for all $m\in\N$ and all sufficiently large $d\in\mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables $m$ is at most $d^{o(1)}$ and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (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, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. 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\"orklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, 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}.
