Algorithms for Arithmetic Circuits.
Neeraj Kayal · Electronic colloquium on computational complexity · 2010
Given a multivariate polynomial f(X) ∈ F[X] as an arithmetic circuit we would like to efficiently determine: 1. Identity Testing. Is f(X) identically zero? 2. Degree Computation. Is the degree of the polynomial f(X) at most a given integer d . 3. 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-algorithm is presented. Finally, randomized polynomial-time algorithms are presented for certain special cases of the third problem.