Abstract
We solve the following algorithmic problems using TC0 circuits, or in logspace and quasilinear time, uniformly in the class of nilpotent groups with bounded nilpotency class and rank: subgroup conjugacy, computing the normalizer and isolator of a subgroup, coset intersection, and computing the torsion subgroup. Additionally, if any input words are provided in compressed form as straight-line programs or in Mal'cev coordinates, the algorithms run in quartic time.
| Original language | English |
|---|---|
| Pages (from-to) | 639-661 |
| Number of pages | 23 |
| Journal | International Journal of Algebra and Computation |
| Volume | 29 |
| Issue number | 4 |
| DOIs | |
| State | Published - 1 Jun 2019 |
Keywords
- Nilpotent groups
- compressed words
- logspace
- simultaneous conjugacy
- subgroup intersection
- threshold circuits
Fingerprint
Dive into the research topics of 'Low-complexity computations for nilpotent subgroup problems'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver