Deterministically testing sparse polynomial identities of unbounded degree

We present two deterministic algorithms for the arithmetic circuit identity testing problem. The running time of our algorithms is polynomially bounded in s and m. where s is the size of the circuit and m is all upper bound oil the number monomials with non-zero coefficients in its standard representation. The running time Of Our algorithms also has a logarithmic dependence oil the degree of the polynomial but, since a circuit of size s can only compute polynomials of degree at most 2(s), the running time does not depend on its degree. Before this work. all such deterministic algorithms had a polynomial dependence on the degree and therefore ail exponential dependence oil s. Our first algorithm works over the integers and it requires only black-box access to the given circuit. Though this algorithm is quite simple, the analysis of why it works relies oil Linnik's Theorem, a deep result from number theory about the size of the smallest prime in an arithmetic progression. Our second algorithm, unlike the first, uses elementary arguments and works over any integral domains, but it uses the circuit in a less restricted manner. In both cases the running time has a logarithmic dependence on the largest coefficient of the polynomial. (C) 2008 Elsevier B.V. All rights reserved.