(While preparing this two other bloggers wrote on the same topic, Scott here and Lipton/Regan here. Our slogan: Complexity Blog: You heard it here THIRD.)
Let w be the exponent for matrix mult. A very brief history of Matrix Multiplication (years given are years of publication, though it is odd to say Pan in 1978 showed that w < 2.796 since, for all I know, he did it in 1977 or even earlier.)
- The obvious way to do this shows w ≤ 3. This is obvious to us; however, I wonder when it was first stated.
- Strassen in 1969 showed w ≤ 2.808. This is important since it shows that Gaussian Elimination is not optimal (that is the name of the paper) and also because it is a cautionary tale for lower bounds- w=3 seems optimal... but its not!
- Pan in 1978 showed that w < 2.796.
- Bini, Capovani, Romani, Lotti in 1979 showed w < 2.78.
- Schonhage in 1981 showed w < 2.522 This was significant since it used a brand new technique.
- Romani in 1982 showed w < 2.517.
- Coppersmith and Winograd in 1981 obtained w < 2.496. This was significant in that it broke the 2.5 barrier.
- Strassen in 1986, using a very diff technique, obtained w < 2.479.
- Coppersmith and Winograd in 1987 obtained w < 2.376. (See here for the Journal Version.) This paper uses the large 3-free sets of Behrend. (See here for Behrends article (it might now work- its the Proceedings of Nat Academy of Sciences website and I don't know if its free to ALL or just to some schools.) or here for my survey of large 3-free sets.)
- Cohn and Umans in 2003 proposed a group theoretic approach which had the potential for new algorithms. Kleinberg and Szegedy in 2005 obtained new algorithms using the approach, but couldn't beat 2.376.
- Elkin in 2008 (here) obtained larger 3-free sets than Behrends. Elkin in 2010 (here) used these sets to get a logv improvement over CW for some v > 0.
- Andy Stothers 2010 PhD thesis (here) claims to have w ≤ 2.374. The result was not stated in the abstract. He didn't post a preprint or email a blogger so this work was relatively unknown. He did tell some experts in the field. (See the comments on Scott's blog for what might be the full story on that).
- This is clearly a breakthrough! There had been NO improvement in two decades!
- The improvement is small; however, it may lead to more improvements (this seems to be common in this field).
- Can Elkin's 3-free sets be used to get a log improvement over Virginia's result? Not sure we care- from what I understand (which is not much) (1) the current techniques can likely be pushed further, and (2) Elkin's 3-free sets will only give a log-ish improvement, no more. (Is log-ish a new word? Should it be?)
- Is the algorithm practical? I suspect not.
- Two breakthroughs in theory within a year from the same family. Impressive!