Big news! It looks like Laci Babai has a quasipolynomial time algorithm for Graph Isomorphism (GI).
That is, GI has jumped from the best known algorithm being almost exponential, to being almost polynomial!
But, of course, you probably already heard about this.
This was the point when I realized that “Oh yeah, I have a blog too. And it’s kinda supposed to be about TCS. And a good deal of people follow TCS blogs because they talk about recent TCS results and give a feel for the landscape…”
For some reason that wasn’t immediately obvious to me and I just posted it to Facebook and unconsciously assumed the big boys would take care of it in the blogs (we seriously need more women bloggers…assuming we need any bloggers at all). But I suppose if I want this blog to have any semblance of legitimacy I should note results that excite me.
Well I guess it’s not a big deal I missed this one result…It only might be “the theoretical computer science result of the decade.” Well, better late than never I suppose. Here it is, cold off the press!
So GI is one of those weird problems that’s not NP-complete (without collapsing the polynomial hierarchy) but also isn’t known to be in P. It’s this intermediate problem. And it’s been an open question for a long time as to where exactly GI is.
It’s generally been the flagship of intermediate problems of NP. Some of its bed-mates are the well-loved problems of factoring and discrete log and lattice problems. Thankfully, unlike all of these bed-mates, GI is not used as the basis of any cryptographic protocol…otherwise this would be a scary result. But this is because we haven’t really thought of GI as a hard problem for quite some time. So Laci’s result isn’t all that conceptually surprising (all though a large chunk of complexity theory is trying to prove things that we all believe are true and wouldn’t be that surprised when we confirm them, yet we consistently fail and so this result is quite exciting).
GI is solved pretty easily in practice. That is, instances of GI that arise in the real world seem to be solved pretty nicely and so it is much unlike its cryptographic bed-mates since they seem to be hard on average.
So, now that GI is within striking distance of a polynomial time result, it should be noted that there wouldn’t be much change to the complexity landscape if we get GI in P. It would be a huge result! But mostly because it has been a longstanding open question and would give us a definitive and well established place to put GI.
The biggest consequence (besides any technical insights the proof gives us) is that pedagogy would be a little bit trickier in trying to introduce the notion of Zero Knowledge Proof systems. I’m currently TA’ing a graduate crypto course and just last week was able to teach of one of the lectures and, surprise surprise, it was on Interactive Proofs and Zero Knowledge. Oh man, that was fun!
But GI was such a great flagship problem for that! All of the intrigue for its use there kind of fades if we have GI in P. Well, it’s only (possibly) quasipolynomial for now…
That being said, now that it’s almost polynomial, I really want to see it land in P now!
Feel free to post any questions or thoughts on this exciting result!