Revision #2 Authors: Vikraman Arvind, Partha Mukhopadhyay, Raja S

Accepted on: 6th June 2016 11:15

Downloads: 498

Keywords:

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.

Revision #1 Authors: Vikraman Arvind, Partha Mukhopadhyay, Raja S

Accepted on: 3rd June 2016 12:18

Downloads: 442

Keywords:

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.

TR16-089 Authors: Vikraman Arvind, Partha Mukhopadhyay, Raja S

Publication: 2nd June 2016 22:56

Downloads: 713

Keywords:

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.