ON THE COMPLEXITY OF COMPUTING CHARACTERS OF FINITE GROUPS
Date
1994-10-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis examines the computational complexity of the problem
of finding the characters of finite groups and some associated problems.
The central focus is how the complexity changes according to how the
group is specified. We examine two extremes. Considering computations
from Cayley tables, when the input size is quadratic in the order of
the input group, we observe that we can efficiently invert Burnside's
character table algorithm to find class matrices.
We also consider computations involving the symmetric group with inputs of
size polylogarithmic in the order of the input group. We show completeness
and hardness results for computations of individual characters of the
symmetric group. Examining the problem of decomposition of outer products
of characters of the symmetric group, we show that a generalization of the
problem is computationally hard. We show that lattice partitions can be
enumerated efficiently.
Description
Keywords
Computer Science