Deterministic black-box identity testing pi-ordered algebraic branching programs

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. An ABP is given by a layered directed acyclic graph with source s and sink t, whose edges are labeled by variables taken from the set {x1, x2,..., xn} or field constants. It computes the sum of weights of all paths from s to t, where the weight of a path is defined as the product of edge-labels on the path. Given a permutation pi of the n variables, for a pi-ordered ABP (pi-OABP), for any directed path p from s to t, a variable can appear at most once on p, and the order in which variables appear on p must respect pi. One can think of OABPs as being the arithmetic analogue of ordered binary decision diagrams (OBDDs). We say an ABP A is of read r, if any variable appears at most r times in A. Our main result pertains to the polynomial identity testing problem, i.e. the problem of deciding whether a given n-variate polynomial is identical to the zero polynomial or not. We prove that over any field F, and in the black-box model, i.e. given only query access to the polynomial, read r pi-OABP computable polynomials can be tested in DTIME[2O(r log r·log2 n log logn)]. In case F is a finite field, the above time bound holds provided the identity testing algorithm is allowe