MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Polynomial Identity Testing via Shifted Partial Derivatives

Michael Forbes
Institute for Advanced Study
Talk
AG 1  
AG Audience
English

Date, Time and Location

Monday, 16 March 2015
09:30
60 Minutes
E2.1
001
Saarbrücken

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 give the first usage of the method of shifted partial derivatives to develop PIT algorithms. In particular, we will highlight the relation to divisibility testing questions, that is, testing whether a given multivariate polynomial f divides another given multivariate polynomial g.

Contact

Karteek Sreenivasaiah
--email hidden
passcode not visible
logged in users only

Karteek Sreenivasaiah, 03/12/2015 13:53 -- Created document.