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
| 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