Parallel identity testing for skew circuits with big powers and applications

DOI10.1007/978-3-662-48054-0_37MaRDI QIDQ2946414zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, D. König

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

Mathematics Subject Classification ID

Extensions, wreath products, and other compositions of groups (20E22) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

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$.

Recommendations

• Parallel identity testing for skew circuits with big powers and applications
• Evaluation of circuits over nilpotent and polycyclic groups
• Evaluating matrix circuits
• The power of depth 2 circuits over algebras
• Deterministic polynomial identity testing in non-commutative models

Cites work

• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Algorithmics on SLP-compressed strings: a survey
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Evaluating matrix circuits
• Finite Monoids: From Word to Circuit Evaluation
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• On the algorithmic insolvability of the word problem in group theory
• On the complexity of pattern matching for highly compressed two-dimensional texts.
• Parallel identity testing for skew circuits with big powers and applications
• Primality and identity testing via Chinese remaindering
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• The Compressed Word Problem for Groups
• The parallel complexity of exponentiating polynomials over finite fields
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Very Fast Parallel Polynomial Arithmetic
• Word Problems and Membership Problems on Compressed Words

Cited in

(7)

• Evaluation of circuits over nilpotent and polycyclic groups
• Parallel identity testing for skew circuits with big powers and applications
• Evaluating matrix circuits
• Equality Testing of Compressed Strings
• Parallel identity testing for skew circuits with big powers and applications
• Emptiness problems for integer circuits
• Cyclotomic identity testing and applications

This page was built for publication: Parallel identity testing for skew circuits with big powers and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946414)