The fast Fourier transform is an algorithm for expanding a function on a cyclic group in a basis of complex exponential functions. In this talk we discuss the generalization of this algorithm to other finite groups, and in particular to symmetric groups. The analysis of the symmetric group algorithm relies on path counting in Young's lattice.
Probability and Combinatorics
Tuesday, March 6, 2001 - 4:30pm
David Maslen
Susquehanna Partners, G.P.