ECCC-Report TR16-193https://eccc.weizmann.ac.il/report/2016/193Comments and Revisions published for TR16-193en-usFri, 25 Nov 2016 22:42:29 +0200
Paper TR16-193
| Identity Testing for +-Regular Noncommutative Arithmetic Circuits |
Vikraman Arvind,
Pushkar Joglekar,
Partha Mukhopadhyay,
Raja S
https://eccc.weizmann.ac.il/report/2016/193An efficient randomized polynomial identity test for noncommutative
polynomials given by noncommutative arithmetic circuits remains an
open problem. The main bottleneck to applying known techniques is that
a noncommutative circuit of size $s$ can compute a polynomial of
degree exponential in $s$ with a double-exponential number of nonzero
monomials. In this paper, which is a follow-up on our earlier article
[AMR16], we report some progress by dealing with two natural
subcases (both allow for polynomials of exponential degree and a
double exponential number of monomials):
(1) We consider \emph{$+$-regular} noncommutative circuits: these
are homogeneous noncommutative circuits with the additional
property that all the $+$-gates are layered, and in each $+$-layer
all gates have the same syntactic degree. We give a
\emph{white-box} polynomial-time deterministic polynomial identity
test for such circuits. Our algorithm combines some new structural
results for $+$-regular circuits with known results for
noncommutative ABP identity testing [RS05PIT], rank bound of
commutative depth three identities [SS13], and equivalence
testing problem for words [Loh15, MSU97, Pla94].
(2) Next, we consider $\Sigma\Pi^*\Sigma$ noncommutative circuits:
these are noncommutative circuits with layered $+$-gates such that
there are only two layers of $+$-gates. These $+$-layers are the
output $+$-gate and linear forms at the bottom layer; between the
$+$-layers the circuit could have any number of $\times$ gates. We
given an efficient randomized \emph{black-box} identity testing
problem for $\Sigma\Pi^*\Sigma$ circuits. In particular, we show if
$f\in\F\angle Z$ is a nonzero noncommutative polynomial computed by
a $\Sigma\Pi^*\Sigma$ circuit of size $s$, then $f$ cannot be a
polynomial identity for the matrix algebra $\mathbb{M}_s(F)$, where
the field $F$ is a sufficiently large extension of $\F$ depending on
the degree of $f$.
Fri, 25 Nov 2016 22:42:29 +0200https://eccc.weizmann.ac.il/report/2016/193