HITTING-SETS FOR ROABP AND SUM OF SET-MULTILINEAR CIRCUITS

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(log2 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(w2)) 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.