Revised: October 4, 2018

Published: October 13, 2019

**Keywords:**algebraic complexity, non-commutative computation, Polynomial Identity Testing, randomized algorithm, Polynomial Indentity Lemma

**Categories:**algorithms, complexity theory, algebraic complexity, noncommutative, Polynomial Identity Testing, polynomials - multivariate, Polynomial Identity Lemma, randomized, arithmetic circuits

**ACM Classification:**F.1.2

**AMS Classification:**68W20

**Abstract:**
[Plain Text Version]

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