Hitting-sets for ROABP and Sum of Set-Multilinear circuits

Abstract

We give a nO(logn)-time (n is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best result known for this class was nO(log2n) due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their exponential dependence on the individual degree. With this, we match the time-complexity for the unknown order ROABP with the known order ROABP (due to Forbes-Shpilka (FOCS 2013)) and also with the depth-3 set-multilinear circuits (due to Agrawal-Saha-Saxena (STOC 2013)). 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. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper, we take a step towards 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 notions of distance and base sets. Distance, for a multilinear depth-3 circuit, measures how far are the partitions from a mere refinement. We design a hitting-set in time nO(dlogn) for d-distance. Further, we give an extension of our result to models where the distance is large but it is small when restricted to certain base sets (of variables). We also explore a new model of ROABP where the factor-matrices are invertible (called invertible-factor ROABP). We design a hitting-set in time poly(nw2) for width-w invertible-factor ROABP. Further, we could do without the invertibility restriction when w=2. Previously, the best result for width-2 ROABP was quasi-polynomial time (Forbes-Saptharishi-Shpilka, STOC 2014).