Back to Search
Start Over
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
- Publication Year :
- 2015
-
Abstract
- 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$.
- Subjects :
- Computer Science - Computational Complexity
20F10, 68Q17, 68W30
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1502.04545
- Document Type :
- Working Paper