ECCC-Report TR10-073https://eccc.weizmann.ac.il/report/2010/073Comments and Revisions published for TR10-073en-usWed, 21 Apr 2010 13:29:25 +0300
Paper TR10-073
| Algorithms for Arithmetic Circuits |
Neeraj Kayal
https://eccc.weizmann.ac.il/report/2010/073Given 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.
Wed, 21 Apr 2010 13:29:25 +0300https://eccc.weizmann.ac.il/report/2010/073