{"id":2521,"date":"2015-11-04T01:00:13","date_gmt":"2015-11-04T06:00:13","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2521"},"modified":"2017-01-12T12:19:07","modified_gmt":"2017-01-12T17:19:07","slug":"g-phi-fo-fum","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2521","title":{"rendered":"G. Phi. Fo. Fum."},"content":{"rendered":"

Update (Dec. 14):<\/strong><\/span> The long wait is over! \u00a0Here’s Laci’s paper on the arXiv<\/a>. \u00a0So far, I’ve read it only deeply enough to note that it contains the following sentence:<\/p>\n

A group G \u2264 S(\u03a9) defines the category of G-isomorphisms of strings on the domain \u03a9; the natural notation for this category, the central object of study in this paper, would seem to be “G-Strings.”<\/p>\n

With that, I believe\u00a0Laci himself has outshone even\u00a0reddit’s attempt<\/a> to mine his breakthrough result for juvenile humor.<\/p>\n

See also a nice Quanta<\/em> article about Laci’s algorithm<\/a> by Erica Klarreich. \u00a0There’s only one statement in the article that I disagree with: namely that, if graph isomorphism were inherently quasipolynomial time, then it would be the first natural example of such a problem. \u00a0We know other natural problems, like approximating free games and socially-optimal Nash equilibria, that are solvable in nO(log n)<\/sup> time but that can’t be in P unless 3SAT is solvable in ~exp(\u221an) time.<\/p>\n

Update (Nov. 17):<\/strong><\/span> Video of Laci’s first talk<\/a> is now available.<\/p>\n

Breaking News (Nov. 12):<\/span><\/b> Jeremy Kun has written up a phenomenal summary<\/a> of Babai’s first lecture. \u00a0I haven’t carefully studied all of it, and in any case, there are many missing details to be filled in later (Babai told Kun that the preprint will be available “soon, soon!”). \u00a0But from the summary, four\u00a0points stood out to me:<\/p>\n

    \n
  1. Babai actually claims a quasipolynomial-time algorithm\u00a0for an interestingly more general problem than graph isomorphism, called string isomorphism<\/em>. \u00a0This was already in the abstract, but googling didn’t reveal what string isomorphism was. \u00a0So, OK, here’s what it is: you’re given two strings x and y over some finite alphabet, as well as the generators of a group G of permutations of the string indices. \u00a0The problem is to determine whether you can transform x to y by applying a permutation in G. \u00a0Or even more generally: given a string x, find a full set of generators for the subgroup of G that fixes x. \u00a0See Kun’s post for the straightforward reductions from GI to these group-theoretic problems.<\/li>\n
  2. As was hinted in the abstract, in Babai’s analysis of\u00a0his algorithm, there’s one step that relies on\u00a0a statement whose only known proof depends\u00a0on\u00a0the Classification of Finite Simple Groups. \u00a0(Thus, it’s not the algorithm itself requires iterating through all the sporadic simple groups or anything like that; this only shows up in\u00a0the correctness proof.) \u00a0This is not<\/em> the first-ever computer-science\u00a0application of the Classification of Finite Simple Groups (indeed, Babai himself has some previous ones), but it’s certainly the most dramatic.<\/li>\n
  3. In previous work on GI, the Johnson graph<\/a> emerged over and over as a forehead-bangingly\u00a0hard case that caused numerous algorithms to fail. \u00a0In the new work, it looks like\u00a0Babai’s central\u00a0technical innovation is to show that, in some sense, the Johnson graph is the only<\/em> obstruction to taking the divide-and-conquer approaches that people that had tried before, and making them run in quasipolynomial time. \u00a0I.e., in each step of the recursion, either<\/em> you can find a Johnson graph on a large fraction of the vertices and handle it specially, or else<\/em>\u00a0you can do something that works whenever there’s not<\/em> a Johnson graph on a large fraction of the vertices. \u00a0Babai calls this “split-or-Johnson.”<\/li>\n
  4. Babai stressed that in some sense, his new algorithm is the culmination of a program laid out by Eugene Luks in 1982. \u00a0Now, the Classification of Finite Simple Groups was also more-or-less\u00a0completed in the early 1980s. \u00a0To my mind, this raises a fascinating socio-mathematical question: which aspects of the new work, if any, could not have been done in the early 80s, possibly by Babai\u00a0or Luks\u00a0themselves? \u00a0what is it that needed\u00a0another 30 years?<\/strong>\u00a0 If the answer turns out to be “nothing,” then to me that’s an astounding\u00a0illustration of the role of the individual in mathematical progress. \u00a0As in: Laci was nice\u00a0enough to take a third-of-a-century break between his and Luks’ work\u00a0in the early 80s, and the “natural next step” in their program … and\u00a0still<\/em>\u00a0no one managed to use that break to beat him to the next step!<\/li>\n<\/ol>\n
    \n

    Earlier today, I was tipped off to\u00a0what might<\/em> be the theoretical computer science result\u00a0of the\u00a0decade. \u00a0My source asked me not to break the news on this blog—but since other theory bloggers<\/a>\u00a0(and<\/a> twitterers<\/a>) are now covering the story, I guess the graph is out of the Babai.<\/p>\n

    According to the University of Chicago’s theory seminar calendar<\/a>, on Tuesday of next week (November 10), the legendary\u00a0Laszlo Babai<\/a> will be giving a talk about a new algorithm that solves the graph isomorphism problem<\/a> in quasipolynomial time. \u00a0The previous fastest algorithm to decide whether two n-vertex graphs G and H are isomorphic—by Babai and Luks, back in 1983—ran in exp(\u221a(n log n)) time. \u00a0If we credit the\u00a0announcement, Babai has now gotten that down to exp(polylog(n)), putting one of the central problems of computer science\u00a0“just barely above\u00a0P<\/a>.” \u00a0(For years, I’ve answered questions on this blog about the status of graph isomorphism—would I bet that it’s in BQP? in coNP? etc.—by saying that, as far as I and many others are concerned, it might as well just be in P. \u00a0Of course I’m happy\u00a0to reaffirm that conjecture tonight.)<\/p>\n

    Next week, I assume, Laci will lecture to a packed house; then the experts\u00a0will race to unpack the details. \u00a0Until then, we probably need to sit tight; I don’t know any more than what’s in the abstract. \u00a0For now,\u00a0I’m delighted\u00a0if commenters want to share\u00a0general thoughts or questions about graph isomorphism (and I’ll try to answer what I can), but I\u00a0won’t<\/em>\u00a0allow uninformed speculations or rumors about the details of the new result—not until Laci has had a chance to speak.<\/p>\n

    \n

    Update (Nov. 5):<\/strong><\/span> While we all wait with bated breath for more details, you can amuse yourself with the talk I gave at Laci’s 60th<\/sup> birthday conference<\/a> five years ago.<\/p>\n

    Also, a comment of mine that I should probably promote to the main post:<\/p>\n

    Dana points out to me that non-native English speakers might not get the staggeringly clever pun in this post\u2019s title (hey, it was the best I could do on a deadline).<\/p>\n

    So, alright, fee fi fo fum<\/a> is what the approaching giant bellows in Jack and the Beanstalk<\/i>. It means something big is on the horizon. Also, G is a graph, and Phi is an isomorphism.<\/p>\n

    \n

    Update (Nov. 12):<\/strong><\/span> So, Laci gave his talk. Video was made but does not appear to be available yet. However, Gabriel Gaster, who was in attendance, graciously live-tweeted everything. Here’s a Storify of the live-tweets.<\/a> (What’s a “Storify”?)<\/p>\n","protected":false},"excerpt":{"rendered":"

    Update (Dec. 14): The long wait is over! \u00a0Here’s Laci’s paper on the arXiv. \u00a0So far, I’ve read it only deeply enough to note that it contains the following sentence: A group G \u2264 S(\u03a9) defines the category of G-isomorphisms of strings on the domain \u03a9; the natural notation for this category, the central object […]<\/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_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-2521","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\/2521","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=2521"}],"version-history":[{"count":9,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2521\/revisions"}],"predecessor-version":[{"id":3114,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2521\/revisions\/3114"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2521"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2521"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2521"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}