  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > DETAIL:

### Paper:

TR10-084 | 14th May 2010 15:05

#### Deterministic Identity Testing of Read-Once Algebraic Branching Programs TR10-084
Authors: Maurice Jansen, Youming Qiao, Jayalal Sarma
Publication: 14th May 2010 16:04
Downloads: 2376
Keywords:

Abstract:

An 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.

ISSN 1433-8092 | Imprint