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