Babai breakthru: graph isomorphism in quasipolynomial time

⭐ 💡 ❗ 😮 😎 😀 ❤ hi all! am very pleased to “announce” (or at least feature) here the GI quasipolynomial time result by Babai. many in the TCS and math community have heard. this post collects/ consolidates many links on the topic circulating so far.

it was very difficult to time this post (maybe about one iota of the difficulty of the proof, lol). it reminds me somewhat of the Zhang breakthrough a few years ago. there is a long dribble of different articles and reactions, and so its hard to figure out an opportune moment/ trigger to post. my final trigger for this post is the Nature article.[a1] and the video of the 1st lecture is now available.[a12]

as the RJLipton blog calls it, its “the world series of complexity theory” or aaronson, “the TCS breakthrough of the decade”. having a result written up in Nature is nearly the pinnacle of achievement in the area as far as media exposure. Nature only occasionally covers theoretical computer science and its typically on very big results. (it would be very interesting to see the list of CS topics covered in Nature and Science over the years.) and these are very big by TCS standards/ metrics: while this problem has been heavily researched for decades, this is the first lower bound advance on the problem in 3 decades— beating Babais own record!

the breakthru is also already covered in Science, Science News, New Scientist, MIT Tech review.[a5][a3][a4][a2] could Babai have envisioned such a massive reaction already? probably not. he turned down an interview with Nature. wow! and who does that? the pressure is really on now. the result is blared largely on his own extremely sterling reputation and long track record of prior meticulous work in the area (over 3 decades of research) because he hasnt published a paper yet.

this is a result that reverberated thru social media very quickly (aka “spreading like wildfire”) with a lot of interest even on reddit.[a8][a10][a11] Gowers cites it on google+ and Tao commented.[b8] there are many blogs on it already by top experts[b] and significant detail in Kuns blog.[b6]

GI was possibly the 1st problem ever called a “disease” in a 1977 paper.[c1] that term is not my favorite at all, but it has stuck somewhat and been refd by many since then. the term represents insider frustration with the problem which maybe doesnt work as great PR… but its evocative and memorable. one wonders what Babai might think of the “disease” moniker. maybe a foremost nontechnical question to ask in an interview when/ if he finally grants one to the media!

have dabbled in GI over the years myself. it has not been one of my major focuses because of its uncertain status relative to NP complete which seems like a bigger open problem. but its in a very close 2nd or 3rd to top CS problems. this problems connection to deep mathematical theory ie group isomorphism means that its very much at the center between a deep CS/Math marriage.

some have mentioned the Classification of Finite Simple Groups (CFSG) and its role in GI and this particular algorithm. Babai himself says the algorithm is not practical to implement. would anyone go through the trouble? hope so! but not even sure if anyone has actually implemented the AKS primality algorithm. a key question, would one have to implement some, part, or all of the CFSG theory to build Babais algorithm? the question/ details of actually implementing the algorithm alone is a very deep one that could probably fill up at least a paper by itself if not several—and a paper Babai is unlikely to write. algorithms in this area are quite abstruse and exist on a very high mathematical plane far from mere applied, mortal programming so to speak.

kun mentions Johnson graphs as playing a key role in the hard instances. could we now see a lot more papers on computational complexity and hardness results of GI on johnson graphs?

its one of those results that only a few in the field (either TCS or math) will be able to initially grasp. it will be picked over by many and hopefully brought down to earth some over the years ahead but such efforts can be slow, timeconsuming and painstaking. and while the top importance of GI is widely regarded in the TCS community, very few people in the world are familiar with the long line of existing results and theory, esp due to the formidable math specialization/ expertise required to understand it.

below are some collected notable/ leading GI refs.[c] this also gives me a great opportunity/ excuse to share a bunch of links longtime collected on the deep connections between (T)CS and group theory, an area that seems likely only to expand significantly in the years and decades ahead, saved almost in anticipation for exactly such a special occasion, although this magnitude exceeds all expectations.[d] (for TCS surveyors/ aficionados/ investigators/ inquirers/ researchers, one might say its almost expected/ forecastable to see some kind of “special event” eventually at some time in this area!) some of the greatest and most highly regarded results in TCS over the decades are connected to group theory.

there are many related high-voted questions on stackexchange with lots of details and refs for leads on eg group theory[e] and GI.[f] theres even a special dedicated tag on cstheory, graph-isomorphism currently with 90 questions. another interesting item/ factoid, GI is (“currently) “2nd on that sites “master list” of top open CS problems behind P vs NP, existence of 1-way functions, and complexity of matrix multiplication.

a bit more musing: the announcement of this result also reminds me a lot of the historic wiles fermat proof. there are some similarities/ parallels. wiles announced his lectures before the paper. he had been working very independently somewhat to the point of isolation (7 years!), disconnected from other researchers. the lecture was jam-packed, and the complex results presented over a series of 3 lectures. but (afaik) no video of his initial lectures exists. so its great/ lucky we live in the internet age and its changing the way such breakthroughs are publicized and recorded— the video lectures will presumably be saved forever. we may be witnessing a historic occasion on the level of the fermat proof.

from the picture, are there any fewer people in Babais lecture than there were in Wiles? there might even be more! ofc serious scientists would scoff at this comparison, but its fun to occasionally revel maybe briefly )( in the rare phenomenon of rock star-like status/ aura/ sheer magnetic/ enthralling audience draw of a theoretical mathematician or computer scientist (maybe only once a decade?). aka celebrated results where the entire community can be proud and congratulatory 😀

so with this stellar result babai is a real live computer science hero comparable to the greats of the field, and if these results are correct they are very likely to lead to a prestigious prize. (ofc he was already an established “hero” to insiders but now the whole world knows it too!) as the saying goes “history in the making” and the wonders of cyberspace now give everyone a front row seat. it may be hard to keep up with further developments but am right now intending to give it shot.

➡ ⭐ 💡 ❗ 😮 (12/15) paper released a few days ago. Graph Isomorphism in Quasipolynomial Time


a. babai
b. blogs
c. GI refs
d. algebraic/groups/fields
e. group theory, stackexchange
f. stackexchange cstheory

3 thoughts on “Babai breakthru: graph isomorphism in quasipolynomial time

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s