We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows:

1. We consider read-once group-products over a finite group $G$, i.e., tests of the form $\prod_{i=1}^n g_{i}^{x_{i}}$ where $g_{i}\in G$, a special case of read-once permutation branching programs. We give generators with ... more >>>