Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-073 | 21st April 2010 11:43

Algorithms for Arithmetic Circuits


Authors: Neeraj Kayal
Publication: 21st April 2010 13:29
Downloads: 2821


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.

ISSN 1433-8092 | Imprint