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 $\mathbb{F}$ computed by a depth-3 $+$-regular circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_s(\mathbb{F})$ when $\mathbb{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).