We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost (nw)^{O(log(n))}, where n is the number of variables and w is the width of the ROABP. Even for a constant-width ROABP, nothing better than a quasi-polynomial bound was known. We improve the hitting-set complexity for the known-order case to n^{O(log(w))}. In particular, this gives the first polynomial time hitting-set for constant-width ROABP (known-order). However, our hitting-set works only over those fields whose characteristic is zero or large enough. To construct the hitting-set, we use the concept of the rank of partial derivative matrix. Unlike previous approaches whose starting point is a monomial map, we use a polynomial map directly. The second case we consider is that of commutative ROABP. The best known hitting-set for this case had cost d^{O(log(w))}(nw)^{O(log(log(w)))}, where d is the individual degree. We improve this hitting-set complexity to (ndw)^{O(log(log(w)))}. We get this by achieving rank concentration more efficiently.

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).

We give an $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious arithmetic branching programs (ROABPs). The best time complexity known for blackbox polynomial identity testing (PIT) for this class was $n^{O(\log^2 n)}$ due to Forbes, Saptharishi, and Shpilka [Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875]. Moreover, their result holds only when the individual degree is small, while we do not need any such assumption. With this, we match the time complexity for the unknown-order ROABP with the known-order ROABP (due to Forbes and Shpilka [Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 243--252]) and also with the depth-3 set-multilinear circuits (due to Agrawal, Saha, and Saxena [Proceedings of the 2013 ACM Symposium on Theory of Computing, 2013, pp. 321--330]). Our proof is simpler and involves a new technique called basis isolation. The depth-3 model has recently gained much importance, as it has become a stepping stone to understanding general arithmetic circuits. Multilinear depth-3 circuits are known to have exponential lower bounds but no polynomial time blackbox identity tests. In this paper, we take a step toward designing such hitting-sets. We give the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-3 circuits. To achieve this, we define the notions of distance and base sets. Distance, for a multilinear depth-3 circuit (say, in $n$ variables and $k$ product gates), measures how far the variable partitions corresponding to the product gates are from being a mere refinement of each other. The 1-distance circuits strictly contain the set-multilinear model, while $n$-distance captures general multilinear depth-3. We design a hitting-set in time $(nk)^{O(\Delta \log n)}$ for $\Delta$-distance. Further, we give an extension of our result to models where the distance is large (close to $n$) but is small when restricted to certain base sets (of variables). We also explore a new model of ROABPs where the factor matrices are invertible (called invertible-factor ROABPs). We design a hitting-set in time poly($n^{w^2}$) for width-$w$ invertible-factor ROABPs. Further, we could do without the invertibility restriction when w=2. Previously, the best result for width-2 ROABPs was quasi-polynomial time [M. A. Forbes, R. Saptharishi, and A. Shpilka, Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 867--875].