Seminar • Algorithms and Complexity • Fast Multivariate Multipoint Evaluation

Please note: This seminar will take place in DC 1304 and online.

Mrinal Kumar, Faculty member
School of Technology and Computer Science, Tata Institute of Fundamental Research

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. A straightforward algorithm for this problem is to just iteratively evaluate the polynomial at each of the inputs. The question of obtaining faster-than-naive (and ideally, close to linear time) algorithms for this problem is a natural and basic question in computational algebra. In addition to its own inherent interest, faster algorithms for multipoint evaluation are closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition.

In this talk, I will briefly survey the state of art for this problem, and discuss some recent improvements and applications.

To attend this seminar in person, please go to DC 1304. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/92379472517.