Summary

A probabilistic or randomized algorithm is an algorithm which employs random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance on average over all possible choices of random bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.

Randomized algorithms have proven to be very useful. They often lead to very simple and very efficient algorithms where no deterministic efficient algorithm is known. A classic example are the randomized primality tests by Solovay and Strassen, and Rabin. Primality testing can be seen as a special case of polynomial identity testing (PIT), which occupies a pivotal position in the theory of arithmetic circuit complexity. The problem is deciding if the output of a given arithmetic circuit is an identically zero polynomial. Being such an elementary problem, identity testing has enjoyed its status of prime importance by appearing in several fundamental results including primality testing, the PCP-Theorem, or the IP = PSPACE result.

A common property of many problems is that they can be transformed into polynomial identities. A prominent example is the perfect matching problem that can be turned into the question whether the determinant of a matrix with variable entries is identically zero. Randomized algorithms check such identities by evaluating these polynomials at random points.

The discovery of useful randomized algorithms directly motivates the question of derandomization: is it really necessary to use randomization or is it possible to replace randomized algorithms by deterministic versions with comparable efficiency? In a major break-through result, Agrawal, Kayal and Saxena derandomized a probabilistic algorithm for primality testing. Since then, the general program of derandomization, has become one of the most active research areas within Computational Complexity.

Unconditional derandomization of randomized complexity classes is now known to entail circuit lower bounds. Since such lower bounds are considered as a very difficult problem, also a general derandomization is expected to be very hard. Nevertheless, we have seen great advances in recent years, that give hope that derandomization of algorithms for specific problems with nice algebraic structure is possible. Derandomization and lower bounds for arithmetic circuits are the research topics of the project.