gorithm

Verizon FiOS is coming to my street

My wife was commenting about all the Verizon trucks around town.  I checked the web, because I was curious what they were doing. How cool is this - my town of Needham MA is one of the first in the country to get Verizon FiOS.  FiOS is their Fiber-to-the-home, with many glorious Mbps of speed. (15 Mbps / 2 up, or 30 Mbps / 5 up).  It is even cheaper than my current cable modem.  We have Comcast at the moment, which just blows.  I've signed up to get my notification email, and I'll be dumping Comcast as the first day I can. I'm pretty geeked out.

Is the exponent of matrix multiplication 2?

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.