The complexity of the annihilating polynomial

Let F be a field and f1,..., fk ∈ F[x1,..., xn] be a set of k polynomials of degree d in n variables over the field F. These polynomials are said to be algebraically dependent if there exists a nonzero k-variate polynomial A(t1,..., tk) ∈ F[t1,..., tk] such that A(f1,..., fk) = 0. A is then called an (f1,..., fk)-annihilating polynomial. Given (f1,..., fk) can we determine the existence of an (f1,..., fk)-annihilating polynomial? Even for the very concise representation of polynomials as arithmetic circuits, there exists an efficient randomized algorithm for doing this. What is the degree of A(t1,..., tk)? We give closely matching upper and lower bounds for the degree of the annihilating polynomial. The degree bounds also provide a PSPACE algorithm for computing A(t1,..., tk). Can A(t1,..., tk) be computed efficiently? We show that it is NP-hard to decide if A(0,..., 0) equals zero and #P-hard to evaluate A(0,..., 0)(mod p) for a given prime p. Even if A(t1,..., tk) cannot be computed efficiently, does there at least exist a small circuit representation of A(t1,..., tk)? We show that A(t1,..., tk) does not admit a small circuit representation unless the polynomial hierarchy collapses. In summary, this means that testing for algebraic dependence is one of those extremely rare problems where determining the existence of an object (the annihilating polynomial in our case) can be done efficiently but the actual computation of the object is provably hard. These results also answer some questions posed by Dvir, Gabizon and Wigderson [DGW07]