{"id":839,"date":"2011-11-28T16:09:01","date_gmt":"2011-11-28T21:09:01","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=839"},"modified":"2017-01-13T12:14:44","modified_gmt":"2017-01-13T17:14:44","slug":"2-373","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=839","title":{"rendered":"2.373"},"content":{"rendered":"

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<\/sup>) steps. \u00a0 Last year, though, in his\u00a0PhD thesis<\/a>, Andrew Stothers gave an improvement to O(n2.374<\/sup>)\u00a0steps. \u00a0And today, \u00a0Virginia Vassilevska Williams<\/a>\u00a0of Berkeley and Stanford, released a paper<\/a> that gives a general methodology for analyzing Coppersmith-Winograd-type algorithms, and that improves the matrix-multiplication time to a lightning-fast O(n2.373<\/strong><\/span><\/sup>) steps.<\/span>\u00a0 (Virgi’s work was independent of Stothers’, though she credits him and applies an idea of his to simplify her proof.) \u00a0Full disclosure: I actually knew a month ago that this was coming—I had a hell of a time keeping the secret. \u00a0I’d recommend that you get started memorizing “\u03c9<2.373,” but as Russell Impagliazzo points out in the comments, the exponent might<\/em> get lowered again in short order. \u00a0Huge congratulations to Virgi and to Andrew for this breakthrough!<\/p>\n

\n

Update (Nov. 30):<\/strong><\/span> Last night I received an extremely gracious email from Andrew Stothers, which he’s given me permission to summarize here. \u00a0In the email, Andrew expressed how excited he was about Virgi’s new result, apologized for the confusion he caused by not mentioning his improvement to \u03c9 until page 71 of his thesis (he says he doesn’t know why he did it), and said that he meant to publish a paper, but was prevented from doing so by health and job issues. \u00a0He also said that he didn’t take issue with anything I wrote here, except<\/em> that I mistakenly referred to him as Andy rather than Andrew. \u00a0In response, I congratulated Andrew on his achievement; expressed how happy I was that—ironically—his work is now finally<\/em> getting some of the attention that it deserves; and promised to buy him a beer when and if I’m ever in Edinburgh, a city I’ve always wanted to visit. \u00a0(On the other hand, I warned Andrew that his LinkedIn profile, which unselfconsciously mentions improvements to his Word and Excel skills as one of the benefits of his PhD research breaching the Coppersmith-Winograd barrier, might have earned him a place in scientific folklore forever!)<\/p>\n

In summary, I now see Andrew as an extraordinarily nice fellow who had some bad luck and—most conspicuously—a lack of good advice<\/em> from people around him. \u00a0I do stand by the points that I was originally trying<\/em>\u00a0to make:<\/p>\n

(a) that this tangled situation shouldn’t in any way<\/em> detract from Virgi’s fantastic achievement, which (except for a simplification, as she discusses) must be considered completely independent of Andrew’s, and<\/p>\n

(b) that there’s indeed an important cautionary lesson for students here, about adequately publicizing your work (yes, there’s\u00a0a happy medium, between hiring a PR firm to wage a viral marketing campaign and burying your solution to a longstanding open problem so far in the body of your PhD thesis that even world experts in the subject who read your thesis will miss it).<\/p>\n

On the other hand, I hereby apologize for anything I said that could even be perceived<\/em> as slighting Andrew, his important work, or his motives.<\/p>\n

\n

Another Update:<\/strong><\/span> On the third hand, if you’re one of the commenters whose beef is not about attribution, but about the entire concept of using a CS theory blog to “promote” major milestones in CS theory (like the breaking of the Coppersmith-Winograd barrier), then I apologize for absolutely nothing. \u00a0Go read an economics or physics blog; I understand that those are entirely hype-free. \u00a0Better yet, go to hell.<\/p>\n","protected":false},"excerpt":{"rendered":"

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. \u00a0 Last year, though, in his\u00a0PhD thesis, Andrew Stothers gave an improvement to O(n2.374)\u00a0steps. \u00a0And today, \u00a0Virginia Vassilevska Williams\u00a0of Berkeley and Stanford, released a paper that gives a general methodology for analyzing Coppersmith-Winograd-type […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[31,5],"tags":[],"class_list":["post-839","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/839","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=839"}],"version-history":[{"count":12,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/839\/revisions"}],"predecessor-version":[{"id":1534,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/839\/revisions\/1534"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=839"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=839"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=839"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}