Polynomial Identity Testing

Given a multivariate polynomial, is it identically zero?
If "given" means that we get a list of coefficients,
then this problem is of course trivial: the polynomial
is zero iff all coefficients are zero.
For this talk, "given" will mean that we only have blackbox
access to the polynomial or we just have a circuit computing
the polynomial.

The later variant, ACIT, is an important problem that is
in co-RP but for which no deterministic polynomial time
algorithm is known. Recently, Kabanets and Impagliazzo showed
that even proving that ACIT is in NP would either yield
a superpolynomial bound for the arithmetic circuit size of
the permanent or the Boolean circuit size of NEXP.
Any of these two results would be a major breakthrough.
Therefore, researchers focused on randomized algorithms for ACIT
with fewer random bits or deterministic algorithms for identity
testing of restricted circuits. We will described some of these
algorithms in the talk.