Tata Institute of Fundamental Research
Fast multivariate multipoint evaluation over finite fields
STCS Seminar
Speaker:
Mrinal Kumar (Indian Institute of Technology Bombay)
Organiser:
Jaikumar Radhakrishnan
Date:
Monday, 30 May 2022, 11:00 to 12:00
Venue:
A-201 and Zoom
(Scan to add to calendar)
Abstract:
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 fundamental 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.
Nearly linear time algorithms have been known for the univariate multipoint evaluation for close to five decades due to a work of Borodin and Moenck but fast algorithms for the multivariate (or, even bivariate) version have been much harder to come by. In a significant improvement to the state of art for this problem in 2008, 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 degree of the input polynomial in every variable.
In this talk, we will discuss two new algorithms for this problem: the first is a simple and natural algebraic algorithm over not-too-large fields of small characteristic and the second is a (non-algebraic) algorithm for this problem over all finite fields. Both these algorithms run 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.
The talk is based on joint works with Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Chandra Kanta Mohapatra and Chris Umans.
| Speaker: | Mrinal Kumar (Indian Institute of Technology Bombay) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Monday, 30 May 2022, 11:00 to 12:00 |
| Venue: | A-201 and Zoom |
(Scan to add to calendar)
Abstract:
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 fundamental 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.
Nearly linear time algorithms have been known for the univariate multipoint evaluation for close to five decades due to a work of Borodin and Moenck but fast algorithms for the multivariate (or, even bivariate) version have been much harder to come by. In a significant improvement to the state of art for this problem in 2008, 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 degree of the input polynomial in every variable.
In this talk, we will discuss two new algorithms for this problem: the first is a simple and natural algebraic algorithm over not-too-large fields of small characteristic and the second is a (non-algebraic) algorithm for this problem over all finite fields. Both these algorithms run 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.
The talk is based on joint works with Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Chandra Kanta Mohapatra and Chris Umans.
Nearly linear time algorithms have been known for the univariate multipoint evaluation for close to five decades due to a work of Borodin and Moenck but fast algorithms for the multivariate (or, even bivariate) version have been much harder to come by. In a significant improvement to the state of art for this problem in 2008, 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 degree of the input polynomial in every variable.
In this talk, we will discuss two new algorithms for this problem: the first is a simple and natural algebraic algorithm over not-too-large fields of small characteristic and the second is a (non-algebraic) algorithm for this problem over all finite fields. Both these algorithms run 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.
The talk is based on joint works with Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Chandra Kanta Mohapatra and Chris Umans.