{"id":8680,"date":"2025-02-24T09:41:13","date_gmt":"2025-02-24T15:41:13","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=8680"},"modified":"2025-02-27T06:21:00","modified_gmt":"2025-02-27T12:21:00","slug":"ryan-williams-strikes-again","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=8680","title":{"rendered":"Ryan Williams strikes again"},"content":{"rendered":"\n<p><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-red-color\">Update (Feb. 27):<\/mark><\/strong> While we&#8217;re on the subject of theoretical computer science, friends-of-the-blog Adam Klivans and Raghu Meka have asked me to publicize that <a href=\"https:\/\/stoc2025theoryfest.netlify.app\/\">STOC&#8217;2025 TheoryFest<\/a>, to be held June 23-27 in Prague, is eagerly seeking proposals for workshops.  The deadline is March 9th.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Because of a recent <a href=\"https:\/\/eccc.weizmann.ac.il\/report\/2023\/174\/\">breakthrough<\/a> by Cook and Mertz on Tree Evaluation, Ryan <a href=\"https:\/\/eccc.weizmann.ac.il\/report\/2025\/017\/\">now shows that<\/a> every problem solvable in t time on a multitape Turing machine is also solvable in close to \u221at space<br><\/li>\n\n\n\n<li>As a consequence, he shows that there are problems solvable in O(n) space that require nearly quadratic time on multitape Turing machines<br><\/li>\n\n\n\n<li>If this could be applied recursively to boost the polynomial degree, then P\u2260PSPACE<br><\/li>\n\n\n\n<li>On Facebook, someone summarized this result as \u201cthere exists an elephant that can\u2019t fit through a mouse hole.\u201d  I pointed out that for decades, we only knew how to show there was a blue whale that didn\u2019t fit through the mouse hole<br><\/li>\n\n\n\n<li>I\u2019ll be off the Internet for much of today (hopefully only today?) because of jury duty!  Good thing you\u2019ll have Ryan\u2019s amazing new paper to keep y\u2019all busy\u2026<\/li>\n<\/ul>\n\n\n\n<p><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-red-color\">Update (Feb. 25):<\/mark><\/strong> It occurs to me that the new result is yet another vindication for Ryan\u2019s style of doing complexity theory\u2014a style that I\u2019ve variously described with the phrases \u201cironic complexity theory\u201d and \u201ccaffeinated alien reductions,\u201d and that\u2019s all about using surprising upper bounds for one thing to derive unsurprising lower bounds for a different thing, sometimes with a vertigo-inducing chain of implications in between. This style has a decidedly retro feel to it: it\u2019s been clear since the 1960s both that there <em>are<\/em> surprising algorithms (for example for matrix multiplication), and that the time and space hierarchy theorems let us prove at least <em>some<\/em> separations. The dream for decades was to go fundamentally beyond that, separating complexity classes by \u201ccracking their codes\u201d and understanding the space of all possible things they can express. Alas, except for low-level circuit classes, that program has largely failed, for reasons partly explained by the Natural Proofs barrier. So Ryan achieves his successes by simply doubling down on two things that <em>have<\/em> worked since the beginning: (1) finding even more surprising algorithms (or borrowing surprising algorithms from other people), and then (2) combining those algorithms with time and space hierarchy theorems in clever ways to achieve new separations.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update (Feb. 27): While we&#8217;re on the subject of theoretical computer science, friends-of-the-blog Adam Klivans and Raghu Meka have asked me to publicize that STOC&#8217;2025 TheoryFest, to be held June 23-27 in Prague, is eagerly seeking proposals for workshops. The deadline is March 9th. Update (Feb. 25): It occurs to me that the new result [&hellip;]<\/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":[5],"tags":[],"class_list":["post-8680","post","type-post","status-publish","format-standard","hentry","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\/8680","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=8680"}],"version-history":[{"count":6,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/8680\/revisions"}],"predecessor-version":[{"id":8692,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/8680\/revisions\/8692"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8680"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8680"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8680"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}