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

DOI10.1007/978-3-319-58747-9_20zbMath1435.20046arXiv1612.05954OpenAlexW2611957621MaRDI QIDQ2399376

Armin Weiß, Svetla Vassileva, Alexei G. Myasnikov

Publication date: 22 August 2017

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

zbMATH Keywords

wreath productsword problemconjugacy problemfree solvable group\({\mathsf {TC}^0}\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Solvable groups, supersolvable groups (20F16) Extensions, wreath products, and other compositions of groups (20E22) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (2)

The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\) ⋮ Knapsack Problems for Wreath Products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Log-space conjugacy problem in the Grigorchuk group
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• Threshold circuits of small majority-depth
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• 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
• On a theorem of Marshall Hall
• Polynomial time conjugacy in wreath products and free solvable groups
• 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
• Authentication from Matrix Conjugation
• Magnus embedding and algorithmic properties of groups 𝐹/𝑁^{(𝑑)}
• The Conjugacy Problem in Wreath Products and Free Metabelian Groups

This page was built for publication: The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)