Parallel identity testing for skew circuits with big powers and applications
Daniel König, Markus Lohrey · International Journal of Algebra and Computation · 2018
Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labeled with powers [Formula: see text] for binary encoded numbers [Formula: see text]. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to [Formula: see text], 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 [Formula: see text]; 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 [Formula: see text]. Using the Magnus embedding, it follows that the compressed word problem for a free metabelian group belongs to [Formula: see text].