Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-084 | 14th May 2010 15:05

Deterministic Identity Testing of Read-Once Algebraic Branching Programs


Authors: Maurice Jansen, Youming Qiao, Jayalal Sarma
Publication: 14th May 2010 16:04
Downloads: 3206


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