Parallel identity testing for skew circuits with big powers and applications

DOI10.1142/S0218196718500431MaRDI QIDQ4687480zbMATH OpenOpenAlexWikidataFDO

Authors Markus Lohrey, D. 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

arithmetic circuitspolynomial identity testingstraight-line programswreath products

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)

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
• On the parallel complexity of linear groups

Cites work

• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A taxonomy of problems with fast parallel algorithms
• Algorithmics on SLP-compressed strings: a survey
• Computational Complexity
• Computing Algebraic Formulas Using a Constant Number of Registers
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Evaluation of circuits over nilpotent and polycyclic groups
• Finite Monoids: From Word to Circuit Evaluation
• 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 finitely generated soluble linear groups
• 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
• 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

(10)

• Evaluation of circuits over nilpotent and polycyclic groups
• Compression techniques in group theory
• Emptiness problems for integer circuits
• Parallel identity testing for skew circuits with big powers and applications
• Evaluating matrix circuits
• The power word problem
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Identity testing for radical expressions
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Streaming word problems

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 Q4687480)