ECCC-Report TR16-089https://eccc.weizmann.ac.il/report/2016/089Comments and Revisions published for TR16-089en-usMon, 06 Jun 2016 11:15:03 +0300
Revision 2
| Randomized Polynomial Time Identity Testing for Noncommutative Circuits |
Vikraman Arvind,
Partha Mukhopadhyay,
Raja S
https://eccc.weizmann.ac.il/report/2016/089#revision2In 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.Mon, 06 Jun 2016 11:15:03 +0300https://eccc.weizmann.ac.il/report/2016/089#revision2
Revision 1
| Randomized Polynomial Time Identity Testing for Noncommutative Circuits |
Vikraman Arvind,
Partha Mukhopadhyay,
Raja S
https://eccc.weizmann.ac.il/report/2016/089#revision1In 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.Fri, 03 Jun 2016 12:18:39 +0300https://eccc.weizmann.ac.il/report/2016/089#revision1
Paper TR16-089
| Randomized Polynomial Time Identity Testing for Noncommutative Circuits |
Vikraman Arvind,
Partha Mukhopadhyay,
Raja S
https://eccc.weizmann.ac.il/report/2016/089In 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.Thu, 02 Jun 2016 22:56:18 +0300https://eccc.weizmann.ac.il/report/2016/089