Low-complexity computations for nilpotent subgroup problems

Jeremy MacDonald, Alexei Miasnikov, Denis Ovchinnikov

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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 languageEnglish
Pages (from-to)639-661
Number of pages23
JournalInternational Journal of Algebra and Computation
Volume29
Issue number4
DOIs
StatePublished - 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