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

Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1

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). Th…