Mrinal Kumar, IIT Bombay

Abstract

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans and Kedlaya-Umans gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables is at most d^{o(1)} where d is the individual degree of the input polynomial.

In this talk, we will describe a natural and simple algebraic algorithm for this problem over not-too-large fields of small characteristic that runs in nearly linear time even when the number of variables is large. We will also discuss an application to an upper bound for data structures for polynomial evaluation and to an upper bound on the rigidity of Vandermonde matrices.

Based on joint work with Vishwas Bhargava, Sumanta Ghosh and Chandra Kanta Mohapatra.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar