The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)

DOI10.1007/s00224-018-9849-2zbMath1453.20045MaRDI QIDQ2311889

Svetla Vassileva, Armin Weiß, Alexei G. Myasnikov

Publication date: 4 July 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-018-9849-2

zbMATH Keywords

wreath products; word problem; conjugacy problem; free solvable group; \(\mathsf{TC}^0\)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20F16: Solvable groups, supersolvable groups

20F05: Generators, relations, and presentations of groups

20E22: Extensions, wreath products, and other compositions of groups

20E05: Free nonabelian groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Related Items

Unnamed Item, Parallel complexity for nilpotent groups, Compression techniques in group theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• Threshold circuits of small majority-depth
• Evaluation of circuits over nilpotent and polycyclic groups
• 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}\)
• Combinatorial group theory and public key cryptography
• Some properties of a Magnus embedding
• On uniformity within \(NC^ 1\)
• Characterizing \(\text{TC}^{0}\) in terms of infinite groups
• Polynomial time conjugacy in wreath products and free solvable groups
• Evolutionary algorithm solution of the multiple conjugacy search problem in groups, and its applications to cryptography
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• New Constructions of Public-Key Encryption Schemes from Conjugacy Search Problems
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• The word and geodesic problems in free solvable groups
• TC^0 circuits for algorithmic problems in nilpotent groups
• Authentication from Matrix Conjugation
• Magnus embedding and algorithmic properties of groups 𝐹/𝑁^{(𝑑)}
• The Conjugacy Problem in Wreath Products and Free Metabelian Groups