{"id":472,"date":"2010-11-08T14:03:57","date_gmt":"2010-11-08T18:03:57","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=472"},"modified":"2019-01-27T05:36:53","modified_gmt":"2019-01-27T11:36:53","slug":"state-of-circuit-lower-bounds-now-slightly-less-humiliating","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=472","title":{"rendered":"State of circuit lower bounds now slightly less humiliating"},"content":{"rendered":"<p>When people want to emphasize how pathetically far we are from proving P\u2260NP, they often use the following argument: <em>for godsakes, we can&#8217;t even prove that NEXP-complete problems aren&#8217;t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates!<\/em><\/p>\n<p>But no more.<\/p>\n<p>As some of you may have heard, recently Ryan Williams achieved a <a href=\"http:\/\/www.cs.cmu.edu\/~ryanw\/acc-lbs.pdf\">breakthrough in circuit lower bounds<\/a>.&nbsp; And as a result, now we <em>can<\/em> prove that NEXP-complete problems aren&#8217;t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates.<\/p>\n<p>More generally, Williams proves that <em>NEXP does not have ACC circuits of third-exponential size<\/em>: that is, size f(n) where f(f(f(n))) is exponential.&nbsp; Here NEXP means nondeterministic exponential time (the exponential-time analogue of NP), and was long a &#8220;barrier class&#8221; for circuit lower bounds.&nbsp; (Note that, if we go even slightly above NEXP, to MA<sub>EXP<\/sub>, then Buhrman, Fortnow, and Thierauf proved in 1998 that MA<sub>EXP<\/sub> doesn&#8217;t have polynomial-size circuits of any depth, and here the polynomial can be improved to half-exponential.)&nbsp; Meanwhile, by &#8220;ACC circuits&#8221; we mean a nonuniform family of constant-depth circuits consisting of AND, OR, NOT, and MOD m gates for arbitrary positive integers m.&nbsp; ACC is another &#8220;barrier class&#8221; for circuit lower bounds: if we go even slightly below it, to AC0[p] (the same as ACC, except that now we only allow MOD p gates for some fixed prime p), then we&#8217;ve known how to prove exponential circuit-size lower bounds since the work of Razborov and Smolensky in the 1980s.<\/p>\n<p>To achieve the combination of NEXP and ACC, Williams implements a program proposed in his <a href=\"http:\/\/www.cs.cmu.edu\/~ryanw\/improved-algs-lbs2.pdf\">previous STOC&#8217;2010 paper<\/a>, for the specific case of ACC.&nbsp; At the core of his lower bound is an <em>algorithm<\/em> for deciding satisfiability of ACC circuits, which does <em>slightly<\/em> (not much) better than brute-force search.&nbsp; (The algorithm relies on, of all things, fast multiplication of rectangular matrices.)&nbsp; While Williams&#8217;s techniques have nothing to do with Mulmuley&#8217;s GCT program, they do fit in well with the Mulmuleyist &#8220;flip&#8221; philosophy of &#8220;proving lower bounds by proving upper bounds.&#8221;<\/p>\n<p>I haven&#8217;t verified Williams&#8217;s proof, but the high-level ideas are compelling&#8212;and while the result is one of the most spectacular of the decade, it&#8217;s not <em>so<\/em> far beyond the current frontier as to strain credulity.&nbsp; Suffice it to say that I won&#8217;t be betting $200,000 against this one.<\/p>\n<p>Congratulations, Ryan!<\/p>\n<p><strong><font color=\"red\">Update:<\/font><\/strong> Amusingly, if you google <a href=\"http:\/\/www.google.com\/search?q=ryan+williams+acc\">Ryan Williams ACC<\/a>, you get a football player of the same name who was apparently Rookie of the Year in the Atlantic Coast Conference.&nbsp; Let&#8217;s all link to Ryan&#8217;s paper from our homepages, and see if we can make <em>our<\/em> &#8220;ACC Rookie of the Year&#8221; win out!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When people want to emphasize how pathetically far we are from proving P\u2260NP, they often use the following argument: for godsakes, we can&#8217;t even prove that NEXP-complete problems aren&#8217;t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates! But no more. As some of you may have heard, recently Ryan Williams achieved a [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","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,"jetpack_post_was_ever_published":false},"categories":[31,5],"tags":[],"class_list":["post-472","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/472","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=472"}],"version-history":[{"count":1,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/472\/revisions"}],"predecessor-version":[{"id":4075,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/472\/revisions\/4075"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=472"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=472"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=472"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}