Theory of Computing ------------------- Title : Randomized Polynomial-Time Identity Testing for Noncommutative Circuits Authors : Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja Volume : 15 Number : 7 Pages : 1-36 URL : https://theoryofcomputing.org/articles/v015a007 Abstract -------- In this paper we show that black-box polynomial identity testing (PIT) for $n$-variate noncommutative polynomials $f$ of degree $D$ with at most $t$ nonzero monomials can be done in randomized $\poly(n,\log t,\log D)$ time, and consequently in randomized $\poly(n,\log t, s)$ time if $f$ is computable by a circuit of size $s$. This result makes progress on a question that has been open for over a decade. Our algorithm is based on efficiently isolating a monomial using nondeterministic automata. The above result does not yield an efficient randomized PIT for noncommutative circuits in general, as noncommutative circuits of size $s$ can compute polynomials with a double-exponential (in $s$) number of monomials. As a first step, we consider a natural class of homogeneous noncommutative circuits, that we call $+$-regular circuits, and give a _white-box_ polynomial-time deterministic PIT for them. These circuits can compute noncommutative polynomials with number of monomials double-exponential in the circuit size. Our algorithm combines some new structural results for $+$-regular circuits with known PIT results for noncommutative algebraic branching programs, a rank bound for commutative depth-3 identities, and an equivalence testing problem for words. Finally, we solve the _black- box_ PIT problem for depth-3 $+$-regular circuits in randomized polynomial time. In particular, we show if $f$ is a nonzero noncommutative polynomial in $n$ variables over the field $\F$ computed by a depth-3 $+$-regular circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $M_s(\F)$ when $\F$ is sufficiently large depending on the degree of $f$. ---------- A preliminary version of this paper appeared in the Proceedings of the 49th ACM Symp. on Theory of Computing (STOC'17).