Breaking the Coppersmith-Winograd Barrier

by Virginia Vassilevska Williams

Oded's comments

Needless to say, I can not verify this exciting result, but I find the approach underlying it very intriguing. This is not the first time that automated methods are used to find good parameters for an algorithm, but still it is an inspiring example. The paper's introduction makes such a nice job in explaining all of this, that I feel I can and should stop here. Indeed, I commend the author for providing such a clear account of issues that are so complex.

The original abstract

The original abstract is quite laconic, merely stating the improvement in the exponent of matrix multiplication (from [CW89]'s 2.376 to the current 2.3727). But do read the paper's introduction.


Back to list of Oded's choices.