ON THE COMPLEXITY OF COMPUTING CHARACTERS OF FINITE GROUPS

dc.contributor.authorHepler, Charles Thomaseng
dc.date.accessioned2008-02-26T22:33:38Z
dc.date.available2008-02-26T22:33:38Z
dc.date.computerscience1999-05-27eng
dc.date.issued1994-10-01eng
dc.description.abstractThis 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.eng
dc.description.notesWe are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.caeng
dc.identifier.department1994-545-14eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30819
dc.identifier.urihttp://hdl.handle.net/1880/45530
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleON THE COMPLEXITY OF COMPUTING CHARACTERS OF FINITE GROUPSeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
1994-545-14.pdf
Size:
8.92 MB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description: