The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)
From MaRDI portal
Publication:2399376
DOI10.1007/978-3-319-58747-9_20zbMath1435.20046arXiv1612.05954MaRDI QIDQ2399376
Armin Weiß, Svetla Vassileva, Alexei G. Myasnikov
Publication date: 22 August 2017
Full work available at URL: https://arxiv.org/abs/1612.05954
68Q25: Analysis of algorithms and problem complexity
20F16: Solvable groups, supersolvable 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
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
