Parallel identity testing for skew circuits with big powers and applications.

Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labeled with powers x n for binary encoded numbers n. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to c o R N C 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 c o R N C 2 ; this result is even new in the one-dimensional case, where the straight-line programs produce words. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products of finitely generated abelian groups belongs to c o R N C 2 . Using the Magnus embedding, it follows that the compressed word problem for a free metabelian group belongs to c o R N C 2 . [ABSTRACT FROM AUTHOR]