ECCC-Report TR10-084https://eccc.weizmann.ac.il/report/2010/084Comments and Revisions published for TR10-084en-usFri, 14 May 2010 16:04:10 +0300
Paper TR10-084
| Deterministic Identity Testing of Read-Once Algebraic Branching Programs |
Maurice Jansen,
Youming Qiao,
Jayalal Sarma
https://eccc.weizmann.ac.il/report/2010/084An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices $s$ and $t$, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from $s$ to $t$, where the weight of a path is taken to be the product of the edge labels on the path. For a read-once ABP every variable appears at most once in the graph. More generally, we consider preprocessed RO-ABPs (PRO-ABP), which are obtained by allowing univariate polynomials on the edges (at most one non-constant polynomial $T_i(x_i)$ per variable $x_i$).
We study the problem of polynomial identity testing sums of $k$ many PRO-ABPs. We obtain the following results, in case edges are labeled by univariate polynomials of degree at most $d$, and provided the underlying field has enough elements (more than $2k^2d^2n^5$ suffices):
1. Given free access to the PRO-ABPs in the sum, we get a deterministic algorithm that runs in time $O(dk^2n^7s^2) + (dn)^{O(k)}$, where $s$ bounds the size of any largest PRO-ABP given on the input.
2. Given black-box access to the PRO-ABPs computing the individual polynomials in the sum, we get a deterministic algorithm that runs in time $k^2(dn)^{O(\log n)} + (dn)^{O(k)}$.
3. Given only black-box access to the polynomial computed by the sum of the $k$ PRO-ABPs, we obtain a $(dn)^{O(k + \log n)}$ time deterministic algorithm.
Items 1. and 3. strengthen two main results of (Shpilka and Volkovich, 2009), who considered polynomial identity testing of sums of $k$ preprocessed read-once formulas.
Fri, 14 May 2010 16:04:10 +0300https://eccc.weizmann.ac.il/report/2010/084