Parallel complexity for nilpotent groups

DOI10.1142/S0218196722500382MaRDI QIDQ5084295zbMATH OpenOpenAlexFDO

Authors Armin Weiß, Alexei 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

\(\mathsf{TC}^0\)greatest common divisorsnilpotent groupssubgroup membership

Mathematics Subject Classification ID

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

Recommendations

• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Low-complexity computations for nilpotent subgroup problems
• Logspace and compressed-word computations in nilpotent groups
• The extended equivalence and equation solvability problems for groups
• On the parallel complexity of linear groups

Cites work

• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• Algorithmic problems for \(\sigma\)-power groups
• Automata, languages and programming. 28th international colloquium, ICALP 2001, Crete, Greece, July 8--12, 2001. Proceedings
• Computational algorithms for deciding some problems for nilpotent groups
• Conjugacy in Nilpotent Groups
• Evaluating matrix circuits
• scientific article; zbMATH DE number 3871623 (Why is no real title available?)
• scientific article; zbMATH DE number 3875506 (Why is no real title available?)
• scientific article; zbMATH DE number 3815938 (Why is no real title available?)
• scientific article; zbMATH DE number 1303030 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 799777 (Why is no real title available?)
• Low-complexity computations for nilpotent subgroup problems
• Nilpotent groups
• Non-commutative lattice problems
• On homomorphisms onto finite groups
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Symbolic Collection using Deep Thought
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• The Post correspondence problem in groups.
• The power word problem
• The word problem
• Two fast parallel GCD algorithms of many integers
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Word Problems Solvable in Logspace

Cited in

(11)

• The Parallel Complexity of Abelian Permutation Group Problems
• On the parallel complexity of linear groups
• Sylow Subgroups in Parallel
• scientific article; zbMATH DE number 919272 (Why is no real title available?)
• Low-complexity computations for nilpotent subgroup problems
• Logspace and compressed-word computations in nilpotent groups
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• On the complexity of some problems on groups input as multiplication tables
• Batch arguments for \textsf{NP} and more from standard bilinear group assumptions
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• Membership problems in infinite groups

This page was built for publication: Parallel complexity for nilpotent groups

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