gorithm

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.

New Biggest Prime Number

There is a new largest known prime number.  It is the 40th Mersenne prime to be found, which are of the form 2^n -1, with n prime.  The largest known primes are usually of this form. In this case it is 2^20996011 - 1.   

Update: As of September 4, 2006, the 44th Mersenne prime was found, 2^32,582,657-1. 

Check here to be sure this post is up to date.