We give a n O ( log n ) -time ( n is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was n O ( log 2 n ) 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 (say, in n variables and k product gates), measures how far are the partitions from a mere refinement. The 1 -distance strictly subsumes the set-multilinear model, while n -distance captures general multilinear depth- 3 . We design a hitting-set in time ( n k ) O ( log n ) for -distance. Further, we give an extension of our result to models where the distance is large (close to n ) but it is small when restricted to certain base sets (of variables).

We also explore a new model of read-once algebraic branching programs (ROABP) where the factor-matrices are invertible (called invertible-factor ROABP). We design a hitting-set in time poly( n w 2 ) 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).