%0 Journal Article
%T Parallel Identity Testing for Skew Circuits with Big Powers and Applications
%A Daniel K£¿nig
%A Markus Lohrey
%J Computer Science
%D 2015
%I arXiv
%X Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labelled with powers $x^n$ for binary encoded numbers $n$. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to $\mathsf{coRNC}^2$, which generalizes a corresponding result for (standard) skew circuits. Two applications of this result are presented: (i) Equivalence of higher-dimensional straight-line programs can be tested in $\mathsf{coRNC}^2$; this result is even new in the one-dimensional case, where the straight-line programs produce strings. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products of finitely generated abelian groups belongs to $\mathsf{coRNC}^2$.
%U http://arxiv.org/abs/1502.04545v1