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.
Summer 2009: Extending the Condorcet Criterion
Over the last two centuries, voting theorists have developed a seemingly innocuous list of criteria for "good" voting systems. However, Arrow and Gibbard-Satterthwaite have shown that no voting system can satisfy all these criteria simultaneously; thus, in an election one must weigh the relative importance of each criterion. One criterion that some voting theorists have traditionally held holy is the Condorcet criterion. In the late eighteenth century, the Marquis de Condorcet proposed that, in an election consisting of more than two candidates, any candidate winning all head-to-head races should be the winner. Such a winner, if it exists, is called a Condorcet winner. While this criterion seems intuitive, it is a tricky criterion for voting systems to satisfy.
We question the logic of Condorcet's criterion by generalizing and arguably strengthening the concept of a Condorcet winner. We define a Condorcet k-winner to be a candidate who wins every k-way (positional voting based) race with any k-1 of the other candidates in the election. Condorcet k-winners, when they do exist, may differ for varying values of k. Our work has recently focused on finding and characterizing such Condorcet-k paradoxes.
Through the use of representation theory, we have found a useful decomposition of the profile space into irreducible submodules which correspond to different Condorcet-k races. We have uncovered a surprising influence of the Condorcet-2 space on all Condorcet-k outcomes for up to five candidate races. We have also determined the simultaneous existence and non-existence of certain collections of Condorcet-k winners for differing values of k for all elections with up to seven candidates.
Aaron Meyers '10 (Bucknell University) is a mathematics major at Bucknell University. When he's not working on math he enjoys bike racing and cheering on his hometown Pittsburgh sports teams.
Sarah Wolff '10 (Colorado College) is a mathematics major, physics minor, and Spanish minor at Colorado College, with interests in algebra and algebraic topology. Originally from Arlington, Virginia, Sarah plans to attend graduate school in math. She enjoys snowboarding, water skiing, and playing on her college Division I women's soccer team.
Angela Wu '11 (Swarthmore College) is a junior at Swarthmore College where she is an honors major in math and honors minor in economics. Her interests lie in discrete math and theoretical computer science. Originally from Sunnyvale, California, she hopes to attend graduate school in mathematics, but in the meantime she enjoys tennis, flute, and a pearl tea-driven lifestyle.
Note: Aaron, Sarah, and Angela were participants in the 2009 Claremont Colleges REU.
Summer 2008: 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.
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
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.