Back to Search
Start Over
Evaluating Matrix Circuits
- Publication Year :
- 2015
-
Abstract
- The circuit evaluation problem (also known as the compressed word problem) for finitely generated linear groups is studied. The best upper bound for this problem is $\mathsf{coRP}$, which is shown by a reduction to polynomial identity testing. Conversely, the compressed word problem for the linear group $\mathsf{SL}_3(\mathbb{Z})$ is equivalent to polynomial identity testing. In the paper, it is shown that the compressed word problem for every finitely generated nilpotent group is in $\mathsf{DET} \subseteq \mathsf{NC}^2$. Within the larger class of polycyclic groups we find examples where the compressed word problem is at least as hard as polynomial identity testing for skew arithmetic circuits.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1502.03540
- Document Type :
- Working Paper