TR16-193 Authors: Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

Publication: 25th November 2016 22:42

Downloads: 1084

Keywords:

An 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$.