Parallel complexity for nilpotent groups

DOI10.1142/S0218196722500382OpenAlexW4223913419MaRDI QIDQ5084295

Armin Weiß, Alexei G. Myasnikov

Publication date: 24 June 2022

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

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

zbMATH Keywords

nilpotent groupsgreatest common divisors\(\mathsf{TC}^0\)subgroup membership

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nilpotent groups (20F18) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-commutative lattice problems
• The Post correspondence problem in groups.
• Nilpotent groups
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• Algorithmic problems for \(\sigma\)-power groups
• Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
• Evaluating Matrix Circuits
• Word Problems Solvable in Logspace
• Symbolic Collection using Deep Thought
• On homomorphisms onto finite groups
• Low-complexity computations for nilpotent subgroup problems
• TC^0 circuits for algorithmic problems in nilpotent groups
• Two Fast Parallel GCD Algorithms of Many Integers
• Conjugacy in Nilpotent Groups
• Computational algorithms for deciding some problems for nilpotent groups
• The word problem
• Automata, languages and programming. 28th international colloquium, ICALP 2001, Crete, Greece, July 8--12, 2001. Proceedings