Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Polynomial Identity Testing via Shifted Partial Derivatives
Speaker:Michael Forbes
coming from:Institute for Advanced Study
Speakers Bio:
Event Type:Talk
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 16 March 2015
Duration:60 Minutes
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.

Name(s):Karteek Sreenivasaiah
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karteek Sreenivasaiah, 03/12/2015 01:53 PM
Last modified:
Uwe Brahm/MPII/DE, 03/16/2015 04:01 AM
  • Karteek Sreenivasaiah, 03/12/2015 01:53 PM -- Created document.