# Deterministic Black-Box Identity Testing $π$-Ordered Algebraic Branching Programs - Computer Science > Computational Complexity

Deterministic Black-Box Identity Testing $π$-Ordered Algebraic Branching Programs - Computer Science > Computational Complexity - Download this document for free, or read online. Document in PDF available to download.

Abstract: In this paper we study algebraic branching programs ABPs with restrictionson the order and the number of reads of variables in the program. Given apermutation $\pi$ of $n$ variables, for a $\pi$-ordered ABP $\pi$-OABP, forany directed path $p$ from source to sink, a variable can appear at most onceon $p$, and the order in which variables appear on $p$ must respect $\pi$. AnABP $A$ is said to be of read $r$, if any variable appears at most $r$ times in$A$. Our main result pertains to the identity testing problem. Over any field$F$ and in the black-box model, i.e. given only query access to the polynomial,we have the following result: read $r$ $\pi$-OABP computable polynomials can betested in $\DTIME2^{Or\log r \cdot \log^2 n \log\log n}$.Our next set of results investigates the computational limitations of OABPs.It is shown that any OABP computing the determinant or permanent requires size$\Omega2^n-n$ and read $\Omega2^n-n^2$. We give a multilinear polynomial$p$ in $2n+1$ variables over some specifically selected field $G$, such thatany OABP computing $p$ must read some variable at least $2^n$ times. We showthat the elementary symmetric polynomial of degree $r$ in $n$ variables can becomputed by a size $Orn$ read $r$ OABP, but not by a read $r-1$ OABP, forany $0 < 2r-1 \leq n$. Finally, we give an example of a polynomial $p$ and twovariables orders $\pi eq \pi-$, such that $p$ can be computed by a read-once$\pi$-OABP, but where any $\pi-$-OABP computing $p$ must read some variable atleast $2^n$

Author: Maurice Jansen, Youming Qiao, Jayalal Sarma

Source: https://arxiv.org/