Problem: We are given a multivariate polynomial f(X_0, X_1, ..., X_{m-1}) with coefficients from F_p and individual degrees atmost (d-1). For N evaluations points a_1, a_2, ..., a_N, compute f(a_i) for all i in [1, N]
We will first consider the simpler univariate version of this problem (evaluate f(X) at N points). Next, we will discuss the algorithm for the general multivariate version by Kedlaya and Umans.
References:
- https://www.sciencedirect.com/science/article/pii/S0022000074800292
- https://epubs.siam.org/doi/10.1137/08073408X
