| Title | : | Linear Equivalence to Vandermonde Polynomials |
| Speaker | : | Ramya C (IITM) |
| Details | : | Tue, 1 May, 2018 2:00 PM @ A M Turing Hall |
| Abstract: | : | The Polynomial Equivalence Problem is a fundamental problem in algebraic complexity theory and has gained significant attention in the literature [Kayal SODA '11, Kayal STOC '12]. It is the problem of testing if the two given polynomials are equivalent upto linear change of co-ordinates. We say two polynomials f and g are 'linearly equivalent' if g can be obtained from f by applying an invertible linear transformation A on the set of variables of f. Even the most restricted cases of this problem are as hard as graph isomorphism [Agrawal, Saxena '06] and some cases are not even known to be decidable. We study the case when one of the two polynomials is fixed to be the Vandermonde polynomial. Vandermonde matrices are standard matrices used in polynomial interpolation and error correcting codes. Vandermonde polynomial is the determinant of the symbolic Vandermonde matrix. In this talk we will focus on testing if a given polynomial is linearly equivalent to the Vandermonde polynomial. We show a deterministic polynomial time algorithm for the problem when the input polynomial is given as linear factors. In the case when f is given as a black-box, we devise a randomized polynomial time algorithm. In association with the above computational problem we understand the group of symmetries of the Vandermonde polynomial. |
