Hitting sets for multilinear read-once algebraic branching programs, in any order
Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka · 2014
We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in nO(log2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the model of read-once oblivious boolean branching programs with unknown order.