Tata Institute of Fundamental Research

Fast multivariate multipoint evaluation

STCS Student Seminar
Speaker: Shanthanu Suresh Rai (TIFR)
Organiser: Varun Ramanathan
Date: Friday, 15 Mar 2024, 14:30 to 15:30
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 

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