Computer Science/Discrete Mathematics Seminar II

In this talk we will examine 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 see efficient algorithms for the first two of these problems. We will also see that the search version of the last two problems is hard. 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 old and new results and open problems related to these matrices of partial derivatives.