{"id":6745,"date":"2022-10-07T11:01:53","date_gmt":"2022-10-07T16:01:53","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=6745"},"modified":"2022-10-08T00:18:02","modified_gmt":"2022-10-08T05:18:02","slug":"postdocs-matrix-multiplication-and-wsj-yet-more-shorties","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=6745","title":{"rendered":"Postdocs, matrix multiplication, and WSJ: yet more shorties"},"content":{"rendered":"\n

I’m proud to say that Nick Hunter-Jones<\/a> and Matteo Ippoliti<\/a>—both of whom work at the interface between quantum information science and condensed-matter physics (Nick closer to the former and Matteo to the latter)—have joined the physics faculty at UT Austin this year. And Nick, Matteo, and I are jointly seeking postdocs to start in Fall 2023! Please check out our call for applications here.<\/a> The deadline is December 1; you apply through AcademicJobsOnline rather than by emailing me as in past years.<\/p>\n\n\n\n

\n\n\n\n

The big news in AI and complexity theory this week was DeepMind’s AlphaTensor<\/a>, and its automated discovery of new algorithms for matrix multiplication. (See here for the Nature<\/em> paper.<\/a>) More concretely, they’ve used AI to discover (among other things) an algorithm for multiplying 4\u00d74 matrices, over finite fields of characteristic 2, using only 47 scalar multiplications. This beats the 49=7\u00d77 that you’d get from Strassen’s algorithm<\/a>. There are other improvements for other matrix dimensions, many of which work over fields of other characteristics.<\/p>\n\n\n\n

Since I’ve seen confusion about the point on social media: this does not<\/em> improve over the best known asymptotic exponent for matrix multiplication, which over any field, still stands at the human-discovered 2.373 (meaning, we know how to multiply two N\u00d7N matrices in O(N2.373<\/sup>) time, but not faster). But it does<\/em> asymptotically improve over Strassen’s O(N2.81<\/sup>) algorithm from 1968, conceivably even in a way that could have practical relevance for multiplying hundreds-by-hundreds or thousands-by-thousands matrices over F2<\/sub>.<\/p>\n\n\n\n

Way back in 2007, I gave a talk<\/a> at MIT CSAIL’s “Wild and Crazy Ideas Session,” where I explicitly proposed to use computer search to look for faster algorithms for 4\u00d74 and 5\u00d75 matrix multiplication. The response I got at the time was that it was hopeless, since the search space was already too huge. Of course, that was before the deep learning revolution.<\/p>\n\n\n\n

\n\n\n\n

This morning, the Wall Street Journal<\/em> published an article by Karen Hao<\/a> about competition between China and the US in quantum computing. Unfortunately paywalled, but includes the following passage:<\/p>\n\n\n\n

Meanwhile, American academics say it\u2019s gotten harder for Chinese students to obtain visas to conduct quantum research in the U.S. \u201cIt\u2019s become common knowledge that when Chinese students or postdocs come to the U.S., they can\u2019t say they\u2019re doing quantum computing,\u201d says Scott Aaronson, director of the Quantum Information Center at the University of Texas, Austin.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

I’m proud to say that Nick Hunter-Jones and Matteo Ippoliti—both of whom work at the interface between quantum information science and condensed-matter physics (Nick closer to the former and Matteo to the latter)—have joined the physics faculty at UT Austin this year. And Nick, Matteo, and I are jointly seeking postdocs to start in Fall […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","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":true,"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-6745","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\/6745","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=6745"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6745\/revisions"}],"predecessor-version":[{"id":6750,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6745\/revisions\/6750"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6745"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}