Parallel Identity Testing for Skew Circuits with Big Powers and Applications
DOI10.1007/978-3-662-48054-0_37zbMath1400.68090arXiv1502.04545OpenAlexW2128810420MaRDI QIDQ2946414
Publication date: 16 September 2015
Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.04545
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Extensions, wreath products, and other compositions of groups (20E22) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Randomized algorithms (68W20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- On the complexity of pattern matching for highly compressed two-dimensional texts.
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Rational subsets and submonoids of wreath products.
- Algorithmics on SLP-compressed strings: A survey
- Parallel Identity Testing for Skew Circuits with Big Powers and Applications
- Evaluating Matrix Circuits
- On the algorithmic insolvability of the word problem in group theory
- Primality and identity testing via Chinese remaindering
- Very Fast Parallel Polynomial Arithmetic
- The parallel complexity of exponentiating polynomials over finite fields
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
- Finite Monoids: From Word to Circuit Evaluation
- The Compressed Word Problem for Groups
- Word Problems and Membership Problems on Compressed Words
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Parallel Identity Testing for Skew Circuits with Big Powers and Applications
