Low-complexity computations for nilpotent subgroup problems

DOI10.1142/S021819671950019XMaRDI QIDQ4968234zbMATH OpenOpenAlexWikidataFDO

Authors Jeremy Macdonald, Denis Ovchinnikov, Alexei Myasnikov

Publication date 12 July 2019

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

Full work available at URL https://arxiv.org/abs/1706.01092

zbMATH Keywords

compressed wordslogspacenilpotent groupssimultaneous conjugacysubgroup intersectionthreshold circuits

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
• Logspace and compressed-word computations in nilpotent groups
• Parallel complexity for nilpotent groups
• Evaluation of circuits over nilpotent and polycyclic groups
• Finding intersections and normalizers in finitely generated nilpotent groups

Cites work

• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Algorithmics on SLP-compressed strings: a survey
• Decomposability of finitely generated torsion-free nilpotent groups
• Diophantine questions in the class of finitely generated nilpotent groups
• Equations in nilpotent groups.
• Evaluation of circuits over nilpotent and polycyclic groups
• scientific article; zbMATH DE number 3875506 (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 2133330 (Why is no real title available?)
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack problem for nilpotent groups
• Logspace and compressed-word computations in nilpotent groups
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Rational subsets of unitriangular groups.
• Some general algorithms. II: Nilpotent groups
• The Compressed Word Problem for Groups
• Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings

Cited in

(17)

• Evaluation of circuits over nilpotent and polycyclic groups
• Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two
• Non-commutative lattice problems
• On the computability of the terms and quotient groups by them in the upper and lower central series of the computable groups
• The complexity of the isolators of the lower central series in the computable nilpotent groups
• scientific article; zbMATH DE number 4039876 (Why is no real title available?)
• scientific article; zbMATH DE number 1104166 (Why is no real title available?)
• Computer Search for Nilpotent Complexes
• scientific article; zbMATH DE number 919272 (Why is no real title available?)
• Parallel complexity for nilpotent groups
• Compressed decision problems in hyperbolic groups
• Logspace and compressed-word computations in nilpotent groups
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• A nonlinear decomposition method in analysis of some encryption schemes using group automorphisms
• Compressed decision problems in hyperbolic groups
• Semigroup intersection problems in the Heisenberg groups
• Algorithmic problems for class-2 nilpotents MR-groups

This page was built for publication: Low-complexity computations for nilpotent subgroup problems

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