###
Bilateral DFG-DST Project

##
Derandomizing Polynomial Identity Testing and the Isolation Lemma

Manindra Agrawal | | **Thomas Thierauf** |

IIT Kanpur | | Aalen University |

**Summary**

A number of important computational problems are algebraic in nature.
Algorithmic questions about
these problems motivate research in Computational Complexity. In
the past, efforts to understand these problems have led to some of
the most important developments in Complexity Theory. These
problems also lie at the heart of several significant open
problems of current interest.
Some prominent examples include
primality testing,
perfect matching, or
various equivalence problems for certain circuits and branching programs.

The common property of many of these problems is that they can be transformed
into polynomial identities.
Randomized algorithm check such identities by evaluating
these polynomials at random points [Schwartz, Zippel].
This led to the definition of
randomized complexity classes like BPP and RP and provided one of
the earliest examples of the power of randomness in computation.
The celebrated deterministic polynomial-time algorithm of Agrawal,
Kayal and Saxena (AKS) can be viewed as part of a general
program of *derandomization*, one of the most active research
areas within Computational Complexity. Although unconditional
derandomization of randomized complexity classes is now known to
entail circuit lower bounds, the AKS-result inspires
hope that derandomization of algorithms for specific problems with
nice algebraic structure may be possible.
This is the goal of the project.