Hitting sets for multilinear read-once algebraic branching programs, in any order

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n O (log 2 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. We obtain our results by recasting, and improving upon, the ideas of Agrawal, Saha and Saxena [ASS13]. We phrase the ideas in terms of rank condensers and Wronskians , and show that our results improve upon the classical multivariate Wronskian, which may be of independent interest. In addition, we give the first n O (lg lg n ) black-box polynomial identity testing algorithm for the so called model of diagonal circuits. This result improves upon the n Θ(lg n ) -time algorithms given by Agrawal, Saha and Saxena [ASS13], and Forbes and Shpilka [FS13b] for this class. More generally, our result holds for any model computing polynomials whose partial derivatives (of all orders) span a low dimensional linear space.

Authors

• Michael A. Forbes 0001
• Ramprasad Saptharishi
• Amir Shpilka

Keywords

• de-randomization
• polynomial identity testing
• read-once branching programs