Parallel identity testing for skew circuits with big powers and applications

DOI10.1142/S0218196718500431zbMath1400.68091OpenAlexW2808995689MaRDI QIDQ4687480

Markus Lohrey, Daniel König

Publication date: 12 October 2018

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196718500431

zbMATH Keywords

wreath productsstraight-line programsarithmetic circuitspolynomial identity testing

Mathematics Subject Classification ID

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 (4)

Emptiness problems for integer circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Compression techniques in group theory

Cites Work

• Unnamed Item
• Unnamed Item
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• On finitely generated soluble linear groups
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Evaluation of circuits over nilpotent and polycyclic groups
• 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.
• Faster Fully Compressed Pattern Matching by Recompression
• Algorithmics on SLP-compressed strings: A survey
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• Primality and identity testing via Chinese remaindering
• Very Fast Parallel Polynomial Arithmetic
• A taxonomy of problems with fast parallel algorithms
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Computing Algebraic Formulas Using a Constant Number of Registers
• Finite Monoids: From Word to Circuit Evaluation
• Computational Complexity
• 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