Welcome
The Applied Representation Theory Group at Harvey Mudd College is based in the Department of Mathematics and led by Michael Orrison and Nicholas Pippenger. Our work focuses on novel applications of the representation theory of finite groups to various problems in a variety of settings. Recent projects have focused on voting theory, fast Fourier transforms for finite groups, and generalized spectral analysis.
Current Project: Fast Matrix Multiplication
In 1969, Strassen showed that square matrices could be multiplied faster than by the naive algorithm, which has worst-case runtime proportional to the cube of the matrix dimension; the best known exponent of matrix multiplication was reduced from 3 to 2.81. This raised the question of what the best possible exponent of matrix multiplication is. Clearly no algorithm can have algorithmic complexity better than the square of the matrix dimension, since this is the size of the output. It is widely believed that the exponent of matrix multiplication can achieve this lower bound, but the best known algorithm due to Coppersmith and Winograd has only reduced the exponent to 2.38.
A 2003 paper by Henry Cohn and Christopher Umans introduces a group-theoretic approach to matrix multiplication algorithms. Their method is analogous to using the fast Fourier transform to efficiently multiply polynomials: the polynomials are embedded in a group algebra of the integers modulo n, a Fourier transform for this group is applied, and the polynomials are multiplied quickly in the 'frequency domain'. Cohn and Umans proposed a similar embedding of matrices into a group algebra, and in doing so reduced the algorithmic problem to a question about finding infinite families of groups with triples of subsets satisfying certain properties. The best known algorithm of this type achieved an exponent of 2.41. Another paper by Cohn, R. Kleinberg, B. Szegedy and Umans reformulates the question into a combinatorial one, where by finding the largest Strong Uniquely Solveable Puzzle of a given length yields subsets that show the exponent is 2. Currently, the best bound provable by these SUSPs is 2.48.
We are investigating iterated wreath product constructions to try to achieve improved algorithms. In particular, we are looking at the special case of the subsets being subgroups. Also, we are working on multiplying structured matrices using triples of subsets which do not quite satisfy the properties necessary to multiply full matrices.
Current Research Students
Richard Bowen '10 is mathematics major at HMC with interests in
linear algebra and theoretical computer science, and many other fields. His
after-graduation plans are up in the air but probably include graduate
school. In his free time, he likes to program, unicycle, make things
out of duct tape, and read and watch science fiction. When not at
school, he lives in Cincinnati.
Bob Chen '10 is a math major from Thousand Oaks, California,
with an interest in algebra and combinatorics. He hopes to attend
graduate school in mathematics and teach either at the university or
high school level. He enjoys playing clarinet, LAN parties, and
running.
Hendrik Orem '09 is a math major with an interest in algebra,
graph theory and computation. He hopes to pursue a graduate education in
mathematics and eventually teach at the university level. Hendrik is
from Portland, Oregon, and spends his spare time on strategy games,
science fiction and books.
Martijn van Schaardenburg '10 is a math-computer science joint major.
He is mostly interested in algorithms. He has lived in 9 different
cities in 6 different countries over the course of his life. Martijn
likes puzzles, computers, and rock climbing. He is currently trying
to learn to play Go and realizing how difficult it is.