Low-complexity computations for nilpotent subgroup problems

DOI10.1142/S021819671950019XOpenAlexW2963957759WikidataQ128508044 ScholiaQ128508044MaRDI QIDQ4968234

Denis Ovchinnikov, Jeremy Macdonald, Alexei G. 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

nilpotent groupsthreshold circuitslogspacesimultaneous conjugacycompressed wordssubgroup intersection

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)

Related Items

Parallel complexity for nilpotent groups ⋮ Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two ⋮ A NONLINEAR DECOMPOSITION METHOD IN ANALYSIS OF SOME ENCRYPTION SCHEMES USING GROUP AUTOMORPHISMS ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diophantine questions in the class of finitely generated nilpotent groups
• Knapsack problem for nilpotent groups
• Some general algorithms. II: Nilpotent groups
• Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Evaluation of circuits over nilpotent and polycyclic groups
• Algorithmics on SLP-compressed strings: A survey
• Equations in nilpotent groups
• Decomposability of finitely generated torsion-free nilpotent groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Logspace and compressed-word computations in nilpotent groups
• TC^0 circuits for algorithmic problems in nilpotent groups
• Rational subsets of unitriangular groups
• The Compressed Word Problem for Groups