__
TR10-073 | 21st April 2010 11:43
__

#### Algorithms for Arithmetic Circuits

**Abstract:**
Given a multivariate polynomial f(x) in F[x] as an arithmetic circuit we would like to efficiently determine:

(i) [Identity Testing.] Is f(x) identically zero?

(ii) [Degree Computation.] Is the degree of the

polynomial f(x) at most a given integer d.

(iii) [Polynomial Equivalence.] Upto an invertible linear transformation of its variables, is f(x) equal to a given polynomial g(x).

The algorithmic complexity of these problems is studied. Some new algorithms are provided here while some known ones are simplified. For the first problem, a deterministic algorithm is presented for the special case where the input circuit is a "sum of powers of sums of univariate polynomials". For the second problem, a $\coRP^{\PP} $-algorithm is presented. Finally, randomized polynomial-time algorithms are presented for certain special cases of the third problem.