Algebraic Independence and Blackbox Identity Testing

Polynomial Identity Testing (PIT) is the problem of checking whether a given n-variate arithmetic circuit computes the zero polynomial in F[x1,. .., xn]. It is a central question in complexity theory as circuits model computation and PIT leads one to a better understanding of circuits. There are several classical randomized algorithms known [DL78, Sch80, Zip79, CK00, LV98, AB03] that solve PIT. The basic Schwartz-Zippel test is: given a circuit C(x1,. .., xn), check C(a) = 0 for a random a ?¸ F n. Finding a deterministic polynomial time test, however, has been more difficult and is currently open.