Speaker:Vishwas Bhargava

Title

Multivariate Multipoint Evaluation: From Fundamentals to Recent Breakthroughs

Abstract

Suppose you have a multivariate polynomial represented by a coefficient vector of N coefficients, and you intend to evaluate this polynomial at N different points. A straightforward quadratic (N^2 time) algorithm for this problem involves iteratively evaluating the polynomial at each input. The question of obtaining algorithms faster than naive (ideally, nearly linear, i.e., N^{1+o(1)} time) for this problem is a natural and fundamental inquiry in computational algebra. In addition to its inherent interest, faster algorithms for multipoint evaluation are closely related to other crucial questions, such as polynomial factorization, matrix rigidity, and modular composition.

In this talk, I will briefly survey the state-of-the-art for this problem, discussing some recent progress, including a complete resolution of the MME problem over all finite fields, along with its applications.

About Vishwas Bhargava

I am a Mathematics Prestigious Postdoctoral Fellow at the University of Waterloo. I earned my Ph.D. at Rutgers under the guidance of Shubhangi Saraf, and my undergraduate studies were completed at IIT Kanpur. My research interests revolve around the theoretical aspects of computer science, with a keen focus on Computational Complexity theory, Pseudorandomness, and Computational Algebra. I am particularly drawn to problems with an Algebraic or Number Theoretic flavor, contributing insights to these fascinating domains. Beyond academia, I enjoy long-distance running and was once deeply involved in dramatics.