Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Efficient Algorithms for Some Algebraic Problems
Speaker: Neeraj Kayal, DIMACS
Date: Thursday, January 31, 2008 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
In this talk we will look at some computational problems related to polynomials, namely:
(i) Given a polynomial, can we make a linear transformation on the variables and write it as the sum of two independent polynomials. (ii) Is a given set of polynomials algebraically dependent? (iii) Is a given polynomial map a bijective map?
We will give efficient algorithms for the first two of these problems. A common feature of the solutions is that a certain matrix of partial derivatives appears in the solution and analysis even though the problem statement itself seems to have nothing to do with partial derivatives. We will also present some old and new results and some open problems related to matrices of partial derivatives.