Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Abstract

In this paper we show that the black-box polynomial identity testing for noncommutative polynomials $f\in \mathbb{F}⟨z_1,z_2,\cdots ,z_n⟩$ of degree $D$ and sparsity $t$, can be done in randomized $\poly(n,\log t,\log D)$ time. As a consequence, if the black-box contains a circuit $C$ of size $s$ computing $f\in \mathbb{F}⟨z_1,z_2,\cdots ,z_n⟩$ which has at most $t$ non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in $s$ and $n$ and $\log t$. This makes significant progress on a question that has been open for over ten years. The earlier result by Bogdanov and Wee [BW05], using the classical Amitsur-Levitski theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit. Our algorithm is based on automata-theoretic ideas introduced in [AMS08,AM08]. In those papers, the main idea was to construct deterministic finite automata that isolate a single monomial from the set of nonzero monomials of a polynomial $f$ in $\mathbb{F}⟨z_1,z_2,\cdots ,z_n⟩$. In the present paper, since we need to deal with exponential degree monomials, we carry out a different kind of monomial isolation using nondeterministic automata.

As the number of monomials in a noncommutative polynomial which has anarithmetic circuit of size $s$ can actually be doubly exponential in $s$, our result does not imply a randomized polynomial-time identity test for all size s noncommutative circuits. The algorithm works only for noncommutative size s circuits which computes a polynomial with exp(s) many monomials