max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | Polynomial Identity Testing via Shifted Partial Derivatives |
---|---|

Speaker: | Michael Forbes |

coming from: | Institute for Advanced Study |

Speakers Bio: | |

Event Type: | Talk |

Visibility: | D1 We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Monday, 16 March 2015 |
---|---|

Time: | 09:30 |

Duration: | 60 Minutes |

Location: | Saarbrücken |

Building: | E2.1 |

Room: | 001 |

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. |

Name(s): | Karteek Sreenivasaiah |
---|

Video Broadcast: | No | To Location: |
---|

Note: | |
---|---|

Attachments, File(s): |

Created: | 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.