Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

We study the problem of obtaining efficient, deterministic, black-box polynomial identity test-ing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka [RS05]), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting sets for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg2 S), this is analogous (in the terminology of boolean pseudorandomness) to a seed-length of lg2 S, which is the seed length of the pseudorandom generators of Nisan [Nis92] and Impagliazzo-Nisan-Wigderson [INW94] for read-once oblivious boolean branching programs. Thus our work can be seen as an algebraic analogue of these foundational results in boolean pseudorandomness. Our results are stronger for branching programs of bounded width, where we give a hitting set of size exp(lg2 S / lg lgS), corresponding to a seed length of lg2 S / lg lgS. This is in stark contrast to the known results for read-once oblivious boolean branching programs of bounde