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 : http://www.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).