There's an interesting seminar called "Group-Theoretic Algorithms for Matrix Multiplication" coming up at MIT by Bobby Kleinberg. He's co-authored a paper (pdf!) to be presented at the Foundations of Computer Science 2005 conference.
If you try to multiply two nxn matrices by the straightforward algorithm, it takes O(n^3) operations. For some time, there has been work on reducing that exponent of 3 down toward 2. Since matrix multiplication is used in lots of places, this is a very important theoretical problem. In practice, n has to be quite large for one of these fancy algorithms to be faster. The new algorithms often use Fast Fourier Transforms (FFT's), and have chased the exponent down to 2.376.
This paper further develops a group theoretic approach with an exponent of 2.41 (the first time this approach yields an exponent below 3). More importantly, they state two conjectures that would imply an exponent of 2. Now all they have to do is prove one of them :-). And no, I can't follow the math in the paper, just appreciate the significance.
Comments