Low-complexity computations for nilpotent subgroup problems

Jeremy MacDonald, Alexei Miasnikov, Denis Ovchinnikov

Research output: Contribution to journalArticle

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

Fingerprint

Low Complexity
Subgroup
Straight-line Programs
Normalizer
Nilpotency
Computing
Nilpotent Group
Conjugacy
Coset
Quartic
Torsion
Intersection
Class
Form

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Cite this

MacDonald, Jeremy ; Miasnikov, Alexei ; Ovchinnikov, Denis. / Low-complexity computations for nilpotent subgroup problems. In: International Journal of Algebra and Computation. 2019 ; Vol. 29, No. 4. pp. 639-661.
@article{0ca2f16176b44ab295d3ca1788a492e3,
title = "Low-complexity computations for nilpotent subgroup problems",
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.",
author = "Jeremy MacDonald and Alexei Miasnikov and Denis Ovchinnikov",
year = "2019",
month = "6",
day = "1",
doi = "https://doi.org/10.1142/S021819671950019X",
language = "English (US)",
volume = "29",
pages = "639--661",
journal = "International Journal of Algebra and Computation",
issn = "0218-1967",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "4",

}

Low-complexity computations for nilpotent subgroup problems. / MacDonald, Jeremy; Miasnikov, Alexei; Ovchinnikov, Denis.

In: International Journal of Algebra and Computation, Vol. 29, No. 4, 01.06.2019, p. 639-661.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Low-complexity computations for nilpotent subgroup problems

AU - MacDonald, Jeremy

AU - Miasnikov, Alexei

AU - Ovchinnikov, Denis

PY - 2019/6/1

Y1 - 2019/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85060401864&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85060401864&partnerID=8YFLogxK

U2 - https://doi.org/10.1142/S021819671950019X

DO - https://doi.org/10.1142/S021819671950019X

M3 - Article

VL - 29

SP - 639

EP - 661

JO - International Journal of Algebra and Computation

JF - International Journal of Algebra and Computation

SN - 0218-1967

IS - 4

ER -