7 ms·

A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details

238 points by Schiphol 11y ago

ebola1717 11y ago
I learned linear algebra and spectral graph theory from Babai, and he also taught a notoriously difficult combinatorics class. It was a rare privilege to be taught by someone who was doing brilliant research and also cared deeply about undergraduate students.
- deleted 11y ago
  [deleted]
- kevinalexbrown 11y ago
  I sat in on a couple of those classes. At the beginning of the class there were 50-100 people registered. At the end, there were 6 (including graduate students).
  - copperx 11y ago
    He has a fitting surname. Spanish speakers say "bye bye" as "babai".
  - idorosen 11y ago
    50 -> ~10 students standing was my experience with laci's algorithms class. He's still an excellent instructor, though. Willingness to do hours of background and follow-up reading outside of class was a requirement if you wanted to get a deep understanding of the material, and it pays off well. (He was very approachable though, not at all the research professor stereotype.) (HatLab, what a small world... :)
s-phi-nl 11y ago
Prof. Richard Lipton of Georgia Tech has an interesting series of blog posts on this result. See: https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-gr... https://rjlipton.wordpress.com/2015/11/09/the-world-series-of-complexity-theory/ https://rjlipton.wordpress.com/2015/11/09/the-world-series-o... https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomo... I expect he will post more as he gets more information.
- isomorphic 11y ago
  Conjecture from the first link: "Raising questions about other problems. This a surprising result. Is a similar result for factoring around the corner? [...] Placing factoring in this complexity class would be a huge difficulty for cryptography." If factoring is indeed in the quasi-polynomial class, the above may well be the understatement of the decade.
  - shpx 11y ago
    If this really is the case (and I'm highly skeptical), switching from 4096 bit to megabit or gigabit keys would buy us atleast a few years. But all previously encrypted messages would effectively become plain text to anyone with the foresight to save them.
  - moyix 11y ago
    Yeah. But as Scott Aaronson points out, GI has a very different feel to factoring. A randomly chosen number will be hard to factor, but it's actually quite hard to come up with examples of GI that are hard: > But then again, in practice, graph isomorphism has already been “basically in P” for decades! If you have two large graphs for which you actually need to know whether they’re isomorphic, just download NAUTY and run it. > This contrasts with the case of factoring, for which I’d personally say that it remains much less clear whether it should or shouldn’t be in P. http://www.scottaaronson.com/blog/?p=2521#comment-889824 http://www.scottaaronson.com/blog/?p=2521#comment-889824
    - isomorphic 11y ago
      Well, we're resting at least a trillion-USD economy on that "much less clear"; probably more. Given that, bad actors are properly incentivized to work on factoring, and we can take comfort that we haven't yet heard any evidence yet of a (quasi-) polynomial solution. That is assuming someone couldn't keep something like that a secret.
gone35 11y ago
Very nice write-up, Jeremy! Too bad you won't be able to make it to the second talk. Also nice disclaimer at the end: At the time of this writing, Babai’s work has not been peer reviewed, and my understanding of his lectures has large gaps and may be faulty. Do not put your life in danger based on information in this post.
- msie 11y ago
  It really sucks that he can't make the second talk. It was a really good write-up and finding someone who both communicates well and can understand the material is tough.
joewalker 11y ago
In Our Time (BBC R4) did a recent episode called "P vs NP" [1] which talked about graph isomorphism, and might serve as an introduction to this. There's an MP3 download at the link. I don't think it's UK only. [1]: http://www.bbc.co.uk/programmes/b06mtms8 http://www.bbc.co.uk/programmes/b06mtms8
eveningcoffee 11y ago
I also hear that some people use graph isomorphism to compare files, do optical character recognition, and analyze social networks, but it seems highly probable to me that GI is not the central workhorse (or even a main workhorse) in these fields. Can somebody in HN more familiar with this add a comment about this?
- jules 11y ago
  Maybe there is somebody who uses GI to do those things, but that is not a standard method and likely a bad idea. For comparing files the standard method is just a diff based on Levenshtein distance, and the standard methods for character recognition are various forms of machine learning (e.g. SVM, NN).
  - deleted 11y ago
    [deleted]
  - OJFord 11y ago
    Social networks sounds like a likely application though. Consider "Graph A is Alice's network of friends; B is Bob's. Do they know exactly and only the same people?" That might be slightly contrived. But it could be used to indicate how introverted a certain community is!
    - bmm6o 11y ago
      In your hypothetical case the vertices would be labeled by friends' names or ids. So you only have to check whether the obvious isomorphism applies i.e. that the graphs are equivalent as sets.
      - OJFord 11y ago
        Ah, yes that's true of course - I clearly wasn't thinking.. Well, then I can't even contrive an example! Still, it's interesting; I wish I had the background to understand it better.
- 11y ago
lovboat 11y ago
There are 140 comments in the blog of Scot Aaronson about this topic: http://www.scottaaronson.com/blog/?p=2521#comments http://www.scottaaronson.com/blog/?p=2521#comments Personal Opinion: Perhaps the Complexity Hierarchy is going to collapse since intuition is not so clear and perhaps the distance from P to NP is shrinking.
- maweki 11y ago
  This would mean that NP=Co-NP and that there is a polynomial certificate for every Co-NP problem. That is what breaks P=NP for me and I just can't wrap my head around how that would be possible.
  - abetusk 11y ago
    Your comment is a little hard to parse. We could live in a world where there are short proofs that an NP-Complete problem is unsolvable but those short proofs are hard to find (i.e. NP=co-NP but P!=NP) [1]. I think there are other consequences but that's an area I don't know that much about. [1] http://cstheory.stackexchange.com/questions/8087/consequences-of-np-conp-and-p-ne-np http://cstheory.stackexchange.com/questions/8087/consequence...
    - maweki 11y ago
      Well, you've read my implication-arrow the wrong way. Since I don't believe that NP=co-NP (in any case), I can't believe that P=NP because Co-P=P. So if the collapse would happen (what the OP mentioned as a possibility), one implication would be NP=co-NP. I don't believe that so I can't believe in collapse.
- abetusk 11y ago
  I don't know why you would think this. There was strong empirical evidence (in my opinion) for thinking Graph Isomorphism was easy. NAUTY (and SAUCY) were good practical implementations that found solutions efficiently (except for some harder class of graphs, maybe). GI was known to be in NP and co-NP which is usually a red flag that the problem is not NP-Complete. For example, linear programming, integer polynomial factorization and primality testing were all in this NP and co-NP region (also discrete logarithm but that's still open). Though extremely informative, there's no reason that GI is polynomial (or pseudo polynomial) would give serious reason to believe that P is anywhere near NP.
yeukhon 11y ago
For those who have really difficult time to understand this... I find http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory http://news.sciencemag.org/math/2015/11/mathematician-claims... opens a small door. I still have tons of questions, probably due to my failure of completing my complexity class in undergraduate.
crb002 11y ago
Lemmas aside, how is this different than only checking repeated prime cycles in conjunction with one of the existing partition algorithms like NAUTY? Laci personally rejected my note submitted to Information Processing Letters saying the lower bound formula was "trivial", https://oeis.org/A186202 https://oeis.org/A186202
j2kun 11y ago
Update: a video of the first talk has been posted on Laci's website: http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4 http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4

238 points by Schiphol 11y ago

I learned linear algebra and spectral graph theory from Babai, and he also taught a notoriously difficult combinatorics class. It was a rare privilege to be taught by someone who was doing brilliant research and also cared deeply about undergraduate students.

deleted 11y ago
[deleted]
kevinalexbrown 11y ago
I sat in on a couple of those classes. At the beginning of the class there were 50-100 people registered. At the end, there were 6 (including graduate students).
- copperx 11y ago
  He has a fitting surname. Spanish speakers say "bye bye" as "babai".
- idorosen 11y ago
  50 -> ~10 students standing was my experience with laci's algorithms class. He's still an excellent instructor, though. Willingness to do hours of background and follow-up reading outside of class was a requirement if you wanted to get a deep understanding of the material, and it pays off well. (He was very approachable though, not at all the research professor stereotype.) (HatLab, what a small world... :)

s-phi-nl 11y ago

Prof. Richard Lipton of Georgia Tech has an interesting series of blog posts on this result. See: https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/ https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-gr... https://rjlipton.wordpress.com/2015/11/09/the-world-series-of-complexity-theory/ https://rjlipton.wordpress.com/2015/11/09/the-world-series-o... https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomorphism-algorithm/ https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomo... I expect he will post more as he gets more information.

isomorphic 11y ago
Conjecture from the first link: "Raising questions about other problems. This a surprising result. Is a similar result for factoring around the corner? [...] Placing factoring in this complexity class would be a huge difficulty for cryptography." If factoring is indeed in the quasi-polynomial class, the above may well be the understatement of the decade.
- shpx 11y ago
  If this really is the case (and I'm highly skeptical), switching from 4096 bit to megabit or gigabit keys would buy us atleast a few years. But all previously encrypted messages would effectively become plain text to anyone with the foresight to save them.
- moyix 11y ago
  Yeah. But as Scott Aaronson points out, GI has a very different feel to factoring. A randomly chosen number will be hard to factor, but it's actually quite hard to come up with examples of GI that are hard: > But then again, in practice, graph isomorphism has already been “basically in P” for decades! If you have two large graphs for which you actually need to know whether they’re isomorphic, just download NAUTY and run it. > This contrasts with the case of factoring, for which I’d personally say that it remains much less clear whether it should or shouldn’t be in P. http://www.scottaaronson.com/blog/?p=2521#comment-889824 http://www.scottaaronson.com/blog/?p=2521#comment-889824
  - isomorphic 11y ago
    Well, we're resting at least a trillion-USD economy on that "much less clear"; probably more. Given that, bad actors are properly incentivized to work on factoring, and we can take comfort that we haven't yet heard any evidence yet of a (quasi-) polynomial solution. That is assuming someone couldn't keep something like that a secret.

gone35 11y ago

Very nice write-up, Jeremy! Too bad you won't be able to make it to the second talk. Also nice disclaimer at the end: At the time of this writing, Babai’s work has not been peer reviewed, and my understanding of his lectures has large gaps and may be faulty. Do not put your life in danger based on information in this post.

msie 11y ago
It really sucks that he can't make the second talk. It was a really good write-up and finding someone who both communicates well and can understand the material is tough.

joewalker 11y ago

In Our Time (BBC R4) did a recent episode called "P vs NP" [1] which talked about graph isomorphism, and might serve as an introduction to this. There's an MP3 download at the link. I don't think it's UK only. [1]: http://www.bbc.co.uk/programmes/b06mtms8 http://www.bbc.co.uk/programmes/b06mtms8

eveningcoffee 11y ago

I also hear that some people use graph isomorphism to compare files, do optical character recognition, and analyze social networks, but it seems highly probable to me that GI is not the central workhorse (or even a main workhorse) in these fields. Can somebody in HN more familiar with this add a comment about this?

jules 11y ago
Maybe there is somebody who uses GI to do those things, but that is not a standard method and likely a bad idea. For comparing files the standard method is just a diff based on Levenshtein distance, and the standard methods for character recognition are various forms of machine learning (e.g. SVM, NN).
- deleted 11y ago
  [deleted]
- OJFord 11y ago
  Social networks sounds like a likely application though. Consider "Graph A is Alice's network of friends; B is Bob's. Do they know exactly and only the same people?" That might be slightly contrived. But it could be used to indicate how introverted a certain community is!
  - bmm6o 11y ago
    In your hypothetical case the vertices would be labeled by friends' names or ids. So you only have to check whether the obvious isomorphism applies i.e. that the graphs are equivalent as sets.
    - OJFord 11y ago
      Ah, yes that's true of course - I clearly wasn't thinking.. Well, then I can't even contrive an example! Still, it's interesting; I wish I had the background to understand it better.
11y ago

lovboat 11y ago

There are 140 comments in the blog of Scot Aaronson about this topic: http://www.scottaaronson.com/blog/?p=2521#comments http://www.scottaaronson.com/blog/?p=2521#comments Personal Opinion: Perhaps the Complexity Hierarchy is going to collapse since intuition is not so clear and perhaps the distance from P to NP is shrinking.

maweki 11y ago
This would mean that NP=Co-NP and that there is a polynomial certificate for every Co-NP problem. That is what breaks P=NP for me and I just can't wrap my head around how that would be possible.
- abetusk 11y ago
  Your comment is a little hard to parse. We could live in a world where there are short proofs that an NP-Complete problem is unsolvable but those short proofs are hard to find (i.e. NP=co-NP but P!=NP) [1]. I think there are other consequences but that's an area I don't know that much about. [1] http://cstheory.stackexchange.com/questions/8087/consequences-of-np-conp-and-p-ne-np http://cstheory.stackexchange.com/questions/8087/consequence...
  - maweki 11y ago
    Well, you've read my implication-arrow the wrong way. Since I don't believe that NP=co-NP (in any case), I can't believe that P=NP because Co-P=P. So if the collapse would happen (what the OP mentioned as a possibility), one implication would be NP=co-NP. I don't believe that so I can't believe in collapse.
abetusk 11y ago
I don't know why you would think this. There was strong empirical evidence (in my opinion) for thinking Graph Isomorphism was easy. NAUTY (and SAUCY) were good practical implementations that found solutions efficiently (except for some harder class of graphs, maybe). GI was known to be in NP and co-NP which is usually a red flag that the problem is not NP-Complete. For example, linear programming, integer polynomial factorization and primality testing were all in this NP and co-NP region (also discrete logarithm but that's still open). Though extremely informative, there's no reason that GI is polynomial (or pseudo polynomial) would give serious reason to believe that P is anywhere near NP.

yeukhon 11y ago

For those who have really difficult time to understand this... I find http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory http://news.sciencemag.org/math/2015/11/mathematician-claims... opens a small door. I still have tons of questions, probably due to my failure of completing my complexity class in undergraduate.

crb002 11y ago

Lemmas aside, how is this different than only checking repeated prime cycles in conjunction with one of the existing partition algorithms like NAUTY? Laci personally rejected my note submitted to Information Processing Letters saying the lower bound formula was "trivial", https://oeis.org/A186202 https://oeis.org/A186202

j2kun 11y ago

Update: a video of the first talk has been posted on Laci's website: http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4 http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4