⭐ 💡 ❗ 😮 😎 😀 ❤ 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
- 1. Graph-theory breakthrough tantalizes mathematicians : Nature News & Comment
- 2. Claimed Computer Science Breakthrough Downgrades One of the Field’s Most Challenging Problems | MIT Technology Review
- 3. New algorithm cracks graph problem | Science News
- 4. Complex problem made simple sends computer scientists wild | New Scientist
- 5. Mathematician claims breakthrough in complexity theory | Science/AAAS | News
- 6. Google Calendar – Event Details
- 7. Laszlo Babai: talks, November 2015
- 8. “Earlier today, I was tipped off to what might be the theoretical computer science result of the decade.” – Researcher Laszlo Babai claims to have found a quasi-polynomial time algorithm for the graph isomorphism problem. : compsci
- 9. Graph Isomorphism in quasipolynomial time? Link goes to an announcement of a Nov. 10 lecture by Laci Babai at University of Chicago : math
- 10. Babai’s Breakthrough on Graph Isomorphism (xpost/r/compsci/) : math
- 11. Babai’s Breakthrough on Graph Isomorphism (xpost /r/compsci) : algorithms
- 12. Babai GI in Quasi-P time video lecture, UChicago
- 13. Landmark Algorithm Breaks 30-Year Impasse / Quanta mag
- 1. Laci Babai and Graph Isomorphism | in theory
- 2. What does it mean when it’s hard to find hard instances? | in theory
- 3. A Big Result On Graph Isomorphism | Gödel’s Lost Letter and P=NP
- 4. Computational Complexity: Looking forward to the GI result
- 5. The World Series Of Complexity Theory | Gödel’s Lost Letter and P=NP
- 6. A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details | Math ∩ Programming
- 7. Shtetl-Optimized » Blog Archive » G. Phi. Fo. Fum.
- 8. For anyone who would like to know more about Laci Babai’s talk yesterday on the…
- 9. Computational Complexity: A Primer on Graph Isomorphism
- 10. A Little More on the Graph Isomorphism Algorithm/ RJLipton blog
- 1. The graph isomorphism disease – Read – 2006 – Journal of Graph Theory – Wiley Online Library
- 2. Advances on Group Isomorphism | Gödel’s Lost Letter and P=NP
- 3. Reading List: Graph Isomorphism | The Quantum Pontiff
- 4. [1301.1493] Practical graph isomorphism, II
- 5. posts tagged “graph isomorphism”, 33bits blog
- 6. The Group Isomorphism Problem: A Possible Polymath Problem? | Gödel’s Lost Letter and P=NP
- 7. [1507.05841] Itemset Isomorphism: GI-Complete
- 8. Group-Theoretic Algorithms and Graph Isomorphism – Springer
- 9. [1505.03737] Isomorphism Testing for Graphs of Bounded Rank Width
- 10. László Babai, Professor in Computer Science, Mathematics and the Physical Sciences Collegiate Division
- 1. TURING MACHINES TO WORD PROBLEMS / Miller
- 2. Finding a path of length k in O∗ (2k ) time / Williams
- 3. Three Theorems About Growth | Gödel’s Lost Letter and P=NP
- 4. THE WORD PROBLEM AND THE ISOMORPHISM PROBLEM FOR GROUPS / Stillwell
- 5. IEEE Xplore Abstract – Computational complexity and the classification of finite simple groups
- 6. Krohn–Rhodes theory – Wikipedia, the free encyclopedia
- 7. Automata, semigroups and groups: 60 years of synergy / Pin
- 8. Gems of CS: Barrington’s Theorem
- 9. THE COMPLEXITY OF INTERSECTING FINITE AUTOMATA HAVING FEW FINAL STATES / Blondin
- 10. Towards an Algebraic Theory of Boolean Circuits
- 11. Can Group Theory Save Complexity Theory? | Gödel’s Lost Letter and P=NP
- 12. GROWTH IN GROUPS: IDEAS AND PERSPECTIVES HARALD A. HELFGOTT
- 13. Three Theorems About Growth | Gödel’s Lost Letter and P=NP
- 14. boolean functions, invariance groups, and parallel complexity
- 1. reference request – Bridge theorems for group theory and formal languages – Computer Science Stack Exchange
- 2. reference request – Uses of algebraic structures in theoretical computer science – Theoretical Computer Science Stack Exchange
- 3. reference request – TCS oriented refs/survey on group theoretic word problem – Theoretical Computer Science Stack Exchange
- 4. co.combinatorics – Applications of representation theory of the symmetric group – Theoretical Computer Science Stack Exchange
- 5. gr.group theory – Can a group be a universal Turing machine? – MathOverflow
- 6. algorithms – What are some applications of binary finite fields in CS? – Computer Science Stack Exchange
- 7. algorithms – Computing with the Monster – Computer Science Stack Exchange
- 8. co.combinatorics – Applications of representation theory of the symmetric group – Theoretical Computer Science Stack Exchange
- 9. soft question – Abstract algebra for Theoretical Computer Scientists – Theoretical Computer Science Stack Exchange
- 1. cc.complexity theory – Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem – Theoretical Computer Science Stack Exchange
- 2. cc.complexity theory – What evidence is there that Graph Isomorphism is not in $P$? – Theoretical Computer Science Stack Exchange
- 3. cc.complexity theory – On Graph Isomorphism Complete Problems – Theoretical Computer Science Stack Exchange
- 4. cc.complexity theory – Fastest known deterministic algorithm for the undirected Graph Isomorphism problem – Theoretical Computer Science Stack Exchange
- 5. cc.complexity theory – Graph Isomorphism Problem – Theoretical Computer Science Stack Exchange
- 6. cstheory.stackexchange.com/questions/tagged/graph-isomorphism
- 7. cc.complexity theory – What is the current known hardness of Graph Isomorphism? – Theoretical Computer Science Stack Exchange
- 8. ds.algorithms – Gentle introduction to graph isomorphism for bounded valance graphs – Theoretical Computer Science Stack Exchange
- 9. cc.complexity theory – Can graph isomorphism be decided with square root bounded nondeterminism? – Theoretical Computer Science Stack Exchange