{"id":2536,"date":"2017-01-16T08:30:29","date_gmt":"2017-01-16T14:30:29","guid":{"rendered":"http:\/\/blogs.ams.org\/blogonmathblogs\/?p=2536"},"modified":"2017-01-17T15:50:43","modified_gmt":"2017-01-17T21:50:43","slug":"more-graph-isomorphism-drama","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/blogonmathblogs\/2017\/01\/16\/more-graph-isomorphism-drama\/","title":{"rendered":"More Graph Isomorphism Drama"},"content":{"rendered":"
\"Credit:<\/a>

Credit: Martin Grandjean, via Wikimedia<\/a>.<\/p><\/div>\n

That plucky graph isomorphism problem<\/a> is at it again! In November 2015, University of Chicago computer scientist Laszlo Babai announced an algorithm to determine whether two graphs are isomorphic in quasipolynomial time, and there was much rejoicing. (My co-blogger Anna Haensch covered it here at the time<\/span><\/a>.)<\/span><\/p>\n

But earlier this month, University of G\u00f6ttingen and CNRS mathematician Harald Helfgott posted on his blog<\/span><\/a> that he had found an error in the proof, and it looked to be a major one. Babai\u2019s algorithm was still a big improvement over earlier algorithms but only ran at subexponential rather than quasipolynomial time. (Complexity jargon got your head spinning? Check out Jeremy Kun\u2019s primers on Big-O notation<\/span><\/a> and P vs NP<\/span><\/a>. There\u2019s also a Wikipedia page on time complexity<\/span><\/a>. He attended Babai\u2019s talk announcing the result in November 2015 and posted about it then, with a few updates since<\/span><\/a>.)<\/span><\/p>\n

Luckily, Babai has fixed the problem<\/span><\/a>, so people with potentially isomorphic graphs they\u2019d like to check in quasipolynomial time can rejoice once again.<\/span><\/p>\n

I\u2019ve been keeping up with graph isomorphism news by reading Erica Klarreich\u2019s posts<\/span><\/a> about it on the Quanta Magazine Abstractions blog. She explained the error Helfgott found<\/span><\/a> on January 5th and posted an update on the fix nine days later<\/span><\/a>. I am especially fond of her analogy for quasipolynomial time: \u201cVery roughly speaking, his algorithm carries the graph isomorphism problem almost all the way across the gulf between the problems that can\u2019t be solved efficiently and the ones that can \u2014 it\u2019s now splashing around in the shallow water off the coast of the efficiently-solvable problems, whose running time is what computer scientists call \u2018polynomial.\u2019\u201d<\/span><\/p>\n

On Saturday, Helfgott gave a Bourbaki lecture<\/span><\/a> on graph isomorphism. Francophones can watch it on Youtube<\/span><\/a>. (Others can also watch it on Youtube\u00a0but will understand less of it.) I\u2019ll also be keeping an eye on the G\u00f6del\u2019s Lost Letter and P=NP blog. They\u2019ve been covering<\/span><\/a> Babai\u2019s work on the graph isomorphism problem since he announced it, and if the weather cooperated, they just went to a conference<\/span><\/a> where Babai gave a distinguished lecture on the topic.<\/span><\/p>\n

Update, January 17, 2017: As he reports on his blog<\/a>, Helfgott’s Bourbaki article\u00a0is now on\u00a0arXiv<\/a> as well (in French).<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

That plucky graph isomorphism problem is at it again! In November 2015, University of Chicago computer scientist Laszlo Babai announced an algorithm to determine whether two graphs are isomorphic in quasipolynomial time, and there was much rejoicing. (My co-blogger Anna … Continue reading →<\/span><\/a><\/p>\n

<\/div>\n","protected":false},"author":61,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[58],"tags":[657,93,656,116,492],"class_list":["post-2536","post","type-post","status-publish","format-standard","hentry","category-mathematics-and-computing","tag-computational-complexity","tag-computer-science","tag-graph-isomorphism","tag-graph-theory","tag-laszlo-babai"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3tW3N-EU","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts\/2536","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/users\/61"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/comments?post=2536"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts\/2536\/revisions"}],"predecessor-version":[{"id":2541,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/posts\/2536\/revisions\/2541"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/media?parent=2536"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/categories?post=2536"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/blogonmathblogs\/wp-json\/wp\/v2\/tags?post=2536"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}