Monday, November 28, 2011


Scott Aaronson writes:

For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n2.376) steps.   Last year, though, buried deep in his PhD thesis where hardly anyone saw it, Andy Stothers discussed an improvement to O(n2.374) steps.  And today,  Virginia Vassilevska Williams of Berkeley and Stanford, released a breakthrough paper that improves the matrix-multiplication time to a lightning-fast O(n2.373) steps.

...The world will not be the same!

No comments:

Post a Comment