In this paper we show that the black-box polynomial identity testing for
noncommutative polynomials $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ 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}\langle z_1,z_2,\cdots,z_n \rangle$
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}\langle z_1,z_2,\cdots,z_n \rangle$. 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 an arithmetic 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.
In this paper we show that polynomial identity testing for
noncommutative circuits of size $s$, computing a polynomial in
$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm
with running time polynomial in $s$ and $n$. This answers 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}\langle z_1,z_2,\cdots,z_n \rangle$. 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.
Included some figures and added some explanation.
In this paper we show that polynomial identity testing for
noncommutative circuits of size $s$, computing a polynomial in
$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm
with running time polynomial in $s$ and $n$. This answers 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}\langle z_1,z_2,\cdots,z_n \rangle$. 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.
