Ted Spaide

Harvey Mudd College Mathematics 2009

Final Thesis: Branching Diagrams for Group Inclusions Induced by Field Inclusions
Thesis Proposal: Fast Fourier Transforms on Finite Groups
Thesis Advisor: Prof. Michael E. Orrison
Second Reader: Prof. Nicholas J. Pippenger

Fast Fourier Transforms on Finite Groups

A Fourier transform of a finite group G is an isomorphism from the complex group algebra CG to a direct product of complex matrix algebras, which are determined beforehand by the structure of G. Given such an isomorphism, naive application of that isomorphism to an arbitrary element of CG takes time proportional to the square of |G|. A fast Fourier transform on some (family of) groups is an algorithm which computes the Fourier transform of a group G of the family in less than O(|G|^2) time, generally O(|G|log|G|) or O(|G|(log|G|)^2). I attempt to find a fast Fourier transform for some family of groups.