2016/11/22 by Arvind, Vikraman, Joglekar, Pushkar, Mukhopadhyay, Partha +1
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1611.07235
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, 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 +-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 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 ΣΠ^*Σ 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 × gates. We given an efficient randomized black-box identity testing problem for ΣΠ^*Σ circuits. In particular, we show if f∈ F is a nonzero noncommutative polynomial computed by a ΣΠ^*Σ circuit of size s, then f cannot be a polynomial identity for the matrix algebra \mathbbMs(F), where the field F is a sufficiently large extension of F depending on the degree of f.