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

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

Mathematics Subject Classification ID

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

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

• 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?)
• scientific article; zbMATH DE number 7561687 (Why is no real title available?)
• 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
• 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 Post correspondence problem in groups.
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• 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
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups

Cited in

(11)

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

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)