Sponsored by the Rutgers University Department of Mathematics and the

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

**Co-organizers:****Andrew Baxter**, Rutgers University, baxter{at} math [dot] rutgers [dot] edu**Lara Pudwell**, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu**Doron Zeilberger**, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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

Abstract:

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.