Abstract

In this talk we consider the polynomial identity testing (PIT) problem: given an algebraic computation which computes a low-degree multivariate polynomial f, is f identically zero as a polynomial? This problem is of fundamental importance in computer algebra and also captures problems such as computing matchings in graphs. While this problem has a simple randomized algorithm (test whether f is zero at a random evaluation point), it is an active line of pseudorandomness research to develop efficient deterministic PIT algorithms for interesting models of algebraic computation.

A related problem is to develop lower bounds: given a model of algebraic computation, find an explicit polynomial f which is expensive to compute in this model. As efficient deterministic PIT algorithms for a model of algebraic computation can be shown to imply lower bounds for that model, developing lower bounds is often a precursor to developing such PIT algorithms. Recently, a new lower bounds technique called "the method of shifted partial derivatives" has been introduced and has been used to obtain a number of new lower bounds for various models, however its potential for yielding PIT algorithms is largely unexplored.

In this work, we use the method of shifted partial derivatives to develop PIT algorithms. In particular, we use these PIT algorithms to give deterministic algorithms for divisibility testing, that is, testing whether a given multivariate polynomial f divides another given multivariate polynomial g.