Deterministic Identity Testing of Read-Once Algebraic Branching Programs

الأصل · EN

In this paper we study polynomial identity testing of sums of k read-once algebraic branching programs (Σₖ-RO-ABPs), generalizing the work in (Shpilka and Volkovich 2008,2009), who considered sums of k read-once formulas (Σₖ-RO-formulas). We show that Σₖ-RO-ABPs are strictly more powerful than Σₖ-RO-formulas, for any k ≤ n/2, where n is the number of variables. We obtain the following results: 1) Given free access to the RO-ABPs in the sum, we get a deterministic algorithm that runs in time O(k²n⁷s) + nᵒ⁽ᵏ⁾, where s bounds the size of any largest RO-ABP given on the input. This implies we have a deterministic polynomial time algorithm for testing whether the sum of a constant number of RO-ABPs computes the zero polynomial. 2) Given black-box access to the RO-ABPs computing the individual polynomials in the sum, we get a deterministic algorithm that runs in time k²nO(n) + nᵒ⁽ᵏ⁾. 3) Finally, given only black-box access to the polynomial computed by the sum of the k RO-ABPs, we obtain an nO(k + n) time deterministic algorithm.