Title: TC^0 circuits for algorithmic problems in nilpotent groups,
Abstract: Recently, Macdonald et. al. showed that many algorithmic problems for
finitely generated nilpotent groups including computation of normal forms, the
subgroup membership problem, the conjugacy problem, and computation of subgroup
presentations can be done in Logspace. Here we follow their approach and show
that all these problems are complete for the uniform circuit class TC^0 -
uniformly for all r-generated nilpotent groups of class at most c for fixed r
and c. In order to solve these problems in TC^0, we show that the unary version
of the extended gcd problem (compute greatest common divisors and express them
as linear combinations) is in TC^0. Moreover, if we allow a certain binary
representation of the inputs, then the word problem and computation of normal
forms is still in uniform TC^0, while all the other problems we examine are
shown to be TC^0-Turing reducible to the binary extended gcd problem.