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
Speaker:Markus Bläser
coming from:Fachrichtung Informatik - Saarbrücken
Speakers Bio:
Event Type:Joint Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Wednesday, 5 October 2016
Duration:60 Minutes
Building:E1 5
Does randomness help to speed up computation? This is a fundamental question in
computer science. Inspired by early successes like randomized primality tests,
a significant amount of researcher believed for a long time that randomness
indeed helps speeding up computations. In 1997, Impagliazzo and Wigderson proved
that the existence of certain hard to compute functions implies that randomness
can only give a speedup by a polynomial factor. Shortly after this, Agrawal, Kayal,
and Saxena were able to give a deterministic polynomial time primality test.

We still do not know whether for every problem having a randomized polynomial time
algorithm there is also a deterministic polynomial time one.
In this talk, we will look at the flagship problem that has a randomized polynomial
time algorithm, but for which we do not know whether a deterministic one exists:
the so-called polynomial identity testing problem. We are given an arithmetic circuit
computing some polynomial and we want to answer whether this polynomial
is identically zero. While there is an easy randomized algorithm, we do not know
whether a deterministic polynomial time algorithm exists and it can be shown that
the existence of such an algorithm implies lower bounds for circuit size,
a partial converse to the result by Impagliazzo and Wigderson. In this talk,
we will introduce the polynomial identity testing problem and its variants
and give an overview about deterministic algorithms for some special cases.
Name(s):Jennifer Müller
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Jennifer Müller, 09/12/2016 03:42 PM -- Created document.