Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-089 | 6th June 2016 11:14

Randomized Polynomial Time Identity Testing for Noncommutative Circuits

RSS-Feed




Revision #2
Authors: Vikraman Arvind, Partha Mukhopadhyay, Raja S
Accepted on: 6th June 2016 11:15
Downloads: 913
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Revision #1 to TR16-089 | 3rd June 2016 12:18

Randomized Polynomial Time Identity Testing for Noncommutative Circuits





Revision #1
Authors: Vikraman Arvind, Partha Mukhopadhyay, Raja S
Accepted on: 3rd June 2016 12:18
Downloads: 907
Keywords: 


Abstract:

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.



Changes to previous version:

Included some figures and added some explanation.


Paper:

TR16-089 | 2nd June 2016 11:18

Randomized Polynomial Time Identity Testing for Noncommutative Circuits





TR16-089
Authors: Vikraman Arvind, Partha Mukhopadhyay, Raja S
Publication: 2nd June 2016 22:56
Downloads: 1307
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint