TY - JOUR
T1 - Low-complexity computations for nilpotent subgroup problems
AU - MacDonald, Jeremy
AU - Miasnikov, Alexei
AU - Ovchinnikov, Denis
N1 - Publisher Copyright:
© 2019 World Scientific Publishing Company.
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.
KW - Nilpotent groups
KW - compressed words
KW - logspace
KW - simultaneous conjugacy
KW - subgroup intersection
KW - threshold circuits
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 - 10.1142/S021819671950019X
DO - 10.1142/S021819671950019X
M3 - Article
AN - SCOPUS:85060401864
SN - 0218-1967
VL - 29
SP - 639
EP - 661
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 4
ER -