AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

60 Minutes

Saarbrücken

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.

Jennifer Müller

2900

--email hidden

passcode not visible

logged in users only