Hacker News Reader

Comment by FaceKicker | Hacker News Reader

Based on skimming the "our contribution" section of the paper (page 2), it seems like this isn't a new algorithm, but rather a new analysis of the same algorithm (Coopersmith Winograd) that proves a tighter lower bound on its runtime.

Not that that's not a valuable contribution, but the linked article seems kind of misleading, unless I'm misunderstanding the paper...

View on HN

That is sort of true. The approach to constructing an algorithm is not new, being essentially due to Coppersmith-Winograd. They used an algorithm A (which doesn't actually multiply matrices, but from which a matrix multiplication algorithm can be constructed) which yielded omega < 2.39. They noted in their own paper that if the second tensor power of algorithm A is used instead of A when constructing the matrix multiplication algorithm, they get the bound 2.376.

This paper analyses the 8th tensor power of the original algorithm A in what is really a tour-de-force and show that it leads to a better bound. So technically the algorithm (the eight tensor power of the original algorithm that CW used) was "known". The innovation here is showing that this is actually better for constructing a matrix multiplication algorithm than the original or second tensor power algorithms.

This paper is also of interest because it allows analysis of tensor powers of other algorithms. It's probably just the beginning of a slew of new records.

There is no question this is a landmark paper. There has been an enormous amount of work for a very long time on this subject.

For those with infinite patience, there is a slightly simplified version of CW presented here:

http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/MAnd...

> There is no question this is a landmark paper. There has been an enormous amount of work for a very long time on this subject.

I don't doubt that at all (though I personally know nothing about the field), I was only criticizing the linked article.

Yes, what you stated is not incorrect. The linked blog is not terribly clear on what has been done. Unfortunately what has been done is very subtle, so I can't really envisage a good blog article announcing this.

+1 For someone helping us understand this - is there now an implementation (or could someone now given this paper, produce an implementation) that will run in this new time? Or is it just (as FaceKicker asked) a new analysis?

Most likely, it's not a practical algorithm, in the sense that it would yield practical time improvement only for unfeasibly large matrices. It does not matter for theorists, though -- for them it's still important result.

I skimmed the whole paper and came to the same conclusion. Seeing the general approach to analysis is interesting though, at least to a CompSci BA like me.

Reply on news.ycombinator.com