On derandomizing polynomial identity testing

Question

In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x_1,\dots,x_n]$. Derandomizing known efficient randomized algorithms and producing an efficient deterministic algorithm is an important open problem. Is there a complete problem for PIT so that derandomizing identity testing for this one class of polynomials solves this open problem? If not, are there classes of polynomials where this problem is solved and classes where they are open?

Answer 1

[tl;dr] A lot is known, and it is a very active area! [/tl;dr]

It is important to specify the representation of the input polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as arithmetic circuits (a.k.a. straight-line programs). And the general case actually boils down to testing whether a given polynomial is the zero polynomial.

There are two main settings that have been studied: the whitebox case in which one has the arithmetic circuit and can inspect it, and the blackbox case in which one knows some things about the circuit (size, formal degree, ...) but cannot inspect it, only evaluate it on some values.

Here are some of the restrictions on the circuits that have been studied:

• Bounded depth: The depth of a circuit is the longest path from an input to the output gate. Testing circuits of depth $2$ is trivial, depth $3$ is very well understood (completely solved? I do not know...), depth $4$ is also well understood. There are results showing that solving the problem for depth-$3$ and depth-$4$ circuit is almost the same as solving the general case.
• Top/bottom fan-in: For bounded-depth circuits, many results have been proved when the fan-in (or arity, that is the number of inputs to a given gate) of either the top gate or the bottom gates is bounded.
• Other restrictions such as a bound on the number of times a variable is used have also been studied.

This survey by Nitin Saxena is a good source for these results. Note though that it is already more than one year (!) old, and this is a very active area. So the most recent results are not covered.

Finally, there are links between the derandomization of PIT and the derandomization of other problems:

• Noether's Normalization Lemma, by Ketan D. Mulmuley;
• Multivariate Polynomial Factorization, by Swastik Kopparty, Shubhangi Saraf and Amir Shpilka.