...except you dropped off the key piece: "Proposed"
As far as I can tell, the page at the link contains no quasi-polynomial running time algorithm for solving graph isomorphisms, yet that is exactly what the title of this posting now states.
There is only a claimed, or, "proposed", algorithm, as far as I can tell. The details won't be revealed until November 10, apparently.
Could anyone provide a good pointer to an introduction more amenable than e.g. Wikipedia? A brief googling provides a lot of material, but I could use a little curation... and that's the sort of thing that sometimes HN is best for. Thanks!
While the two graphs look different, they are exactly the same.
Quasi-polynomial algorithms, as the name implies, are algorithms that are "almost-polynomial" (ie. slower than polynomial, but faster than exponential).
According to https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomi..., the worst case for a quasi-polynomial algorithm is 2^O(log (n)^c).
From the example it looks as if this can be solved linearly, because the structures obviously match. To intuit that the algorithm must be exponential, imagine the vertices to be balls on wire. You grab one ball pull it up as the root from which you start to compare. Now it is obvious you have to pick a vertex from the other graph as well to be the root nice from which to begin the comparison, if you pick the wrong one the graphs won't match. So you will have to pick every ball and see if its structure matches. For a tree (a graph without cycles) it's plain to see it's exponential: in the worst case you have to pick each vertex from one graph and then compare its children with the other graph, that's N * N operations. When the graph does have cycles, the problem becomes more complex. How much more complex is what this scientist perhaps put a new upper limit on.
What. A. Bombshell. Sorry for the low-content post; but it is no exaggeration to say that this "might be the theoretical computer science result of the decade". I'm dying to see how Babai managed to pull it off.
With the news of the EM drive today, probably he confused himself with unclear notation on line 57 of the proof. ( It would be cool if he pulled it off, but even highly respected scientists make mistakes, and a blog post based on the title of a seminar is nothing to get excited about.)
Good mathematical work is rarely an all or nothing proposition. Many independent ideas are required and when the mathematician is very good it is rare that there will be many mistakes.
So even if there are issues with some aspect of the proof there is usually lots of interesting stuff that can be salvaged. The proof of Fermat's last theorem as originally given is an example. It was wrong, though it got patched later, but the original work was still very exciting I think.
Since you seem knowledgeable about this area, do you know a good algorithm for generating isomorphic forms of a given weighted acyclic directional graph? I would be looking to reduce nesting level and/or total edge count.
I know a guy who may have independently come up with the same or a similar result. He's been keeping it under wraps because he's not a mathematician and hasn't proved it, just come up with the method.
I've advised him to upload his results somewhere as soon as possible because he's been working on this for several years. I'll be very interested to see how their methods differ.
Giving false proofs that GI is in P or a related time class is, I think, a common occupation (see, for example, https://rjlipton.wordpress.com/2009/11/04/on-mathematical-di... ); so, if all you know is that this guy thinks he has a solution to the problem, and if the guy is not a mathematician and doesn't have a proof, then the balance of probabilities is that he's probably mistaken (but there's no harm in making the work publicly available, just in case).
I've seen the method and I have a background in math, just not enough to really help prove it.
I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. Even if his solution isn't polynomial it might be quasi polynomial like this result, in which case the differences would be enlightening.
The most likely case is that my friends work is polynomial but wrong in some obscure way. But it will be interesting nonetheless.
> I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least.
It's hard to tell the running time of an algorithm by testing; an O(1) algorithm is indistinguishable from an O(2^(2^n)) algorithm if you only run them on inputs up to n = 10^(10^(10^(34))), say.
(That sounds facetious, and it kind of is, but it cuts the other way, too: I seem to remember that polynomial-time primality testing isn't used in practice because the constants are so huge that, on 'real-life' inputs, it's impractically worse than probabilistic testing.)
Don't worry, we all have an idea for a method to solve GI in P tucked in the back of a drawer. Best to just let it go. Personally I know where I got stuck many years ago and I'm very excited to see somebody do it for real.
That's super fascinating! I have been studying the graph isomorphism problem for a while now since I actually needed it for a real-world use case, so I'm really psyched to hear that there is a good solution now.
About our use case: We developed an algorithm for creating "semantic diffs" between two source code trees. Starting from a graphical (AST) representation of the source code of an entire software project, such a diff would basically tell you how you can transform one tree into the other using a range of edit operations (e.g. insert, delete, copy, paste, modify). The advantage compared to line-by-line diffs is that the latter work only on the text-level (i.e. "this line has been removed, this other line has been added"), whereas the former can actually tell you what changed on a semantic level (i.e. "this argument was inserted into this function and this variable name was changed").
For big projects, this is quite a computational challenge and can (could) only be solved using approximations and shortcuts. Having a polynomial-time algorithm for this would therefore be a huge deal.
I hope that the proof will soon lead to practical implementations of the algorithm.
Probably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
Yes, they discussed in the comment section of the post that when theoretical computer science researchers have tried to find actual graphs which existing algorithms do not handle well, they had difficulties finding them outside of some very specific (and vanishingly small) classes.
Not really, it's not hard to write a compiler to convert between different programming languages. The challenge is translating between the different semantics of different programming languages (e.g., object-oriented vs. functional, dynamically typed vs. statically typed, etc.).
That's interesting, thanks for sharing! Lisp is probably a natural fit for this kind of diffing since it is literally written as a syntax tree, so it is kind of a natural representation of the language.
Have you seen the paper "Editing Functional Programs Without Breaking Them" by Amsden et al. [1]? It does something similar. It allows you to transform any program (in an idealised typed programming languages) into any other using a small collection of transformation operations. The highlight is that this is possible without compormising typability.
This is also related to patch theory [2, 3, 4, 5, 6], a theory that seeks mathematise version control systems like, and to provide provably correct merging algorithms. Patch theory arose in the context of the DARCS system. [7] connects patch theory with homotopy type theory.
Can anyone give an example of real-world problems that graph isomophism can be used to solve? I am out of my depth here and I might be able to make more sense of it if I had a concrete example to relate these concepts to.
One application is electronic circuit verification. A conceptual circuit diagram needs to be mapped to a specific geometry of components and conductive paths between them. The verification that the circuit diagram matches the layout is a graph isomorphism problem; you need to ensure that you can assign the pre-layout components to the ones in the specific layout, such that all the edges line up with those in the original diagram.
43 comments
[ 5.1 ms ] story [ 98.0 ms ] threadAs far as I can tell, the page at the link contains no quasi-polynomial running time algorithm for solving graph isomorphisms, yet that is exactly what the title of this posting now states.
There is only a claimed, or, "proposed", algorithm, as far as I can tell. The details won't be revealed until November 10, apparently.
Possible Quasi-Polynomial Graph Isomorphism Problem Algorithm Upcoming?
Two graphs are isomorphic if they are "the same" graph, as in, if you renamed the edges, the graph would be the same.
For example, if you have the graphs:
G1: A -> B <-> C G1: C -> B <-> A
The only difference between those graphs is the name of the vertices. If you rename them, you get exactly the same graph back.
The first example from the wikipedia page seems like a nice one: https://en.wikipedia.org/wiki/Graph_isomorphism
While the two graphs look different, they are exactly the same.
Quasi-polynomial algorithms, as the name implies, are algorithms that are "almost-polynomial" (ie. slower than polynomial, but faster than exponential). According to https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomi..., the worst case for a quasi-polynomial algorithm is 2^O(log (n)^c).
For the first, I would expect https://en.m.wikipedia.org/wiki/Graph_isomorphism (different from https://en.m.wikipedia.org/wiki/Graph_isomorphism_problem) is simple enough for laymen, as long as they know what a graph is.
For the second, I would think https://en.m.wikipedia.org/wiki/Quasi-polynomial_time#Quasi-... could give just enough rope to climb out of the pit you are in.
So even if there are issues with some aspect of the proof there is usually lots of interesting stuff that can be salvaged. The proof of Fermat's last theorem as originally given is an example. It was wrong, though it got patched later, but the original work was still very exciting I think.
[1] http://www3.cs.stonybrook.edu/~algorith/implement/nauty/impl...
I've advised him to upload his results somewhere as soon as possible because he's been working on this for several years. I'll be very interested to see how their methods differ.
I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. Even if his solution isn't polynomial it might be quasi polynomial like this result, in which case the differences would be enlightening.
The most likely case is that my friends work is polynomial but wrong in some obscure way. But it will be interesting nonetheless.
It's hard to tell the running time of an algorithm by testing; an O(1) algorithm is indistinguishable from an O(2^(2^n)) algorithm if you only run them on inputs up to n = 10^(10^(10^(34))), say.
(That sounds facetious, and it kind of is, but it cuts the other way, too: I seem to remember that polynomial-time primality testing isn't used in practice because the constants are so huge that, on 'real-life' inputs, it's impractically worse than probabilistic testing.)
About our use case: We developed an algorithm for creating "semantic diffs" between two source code trees. Starting from a graphical (AST) representation of the source code of an entire software project, such a diff would basically tell you how you can transform one tree into the other using a range of edit operations (e.g. insert, delete, copy, paste, modify). The advantage compared to line-by-line diffs is that the latter work only on the text-level (i.e. "this line has been removed, this other line has been added"), whereas the former can actually tell you what changed on a semantic level (i.e. "this argument was inserted into this function and this variable name was changed").
For big projects, this is quite a computational challenge and can (could) only be solved using approximations and shortcuts. Having a polynomial-time algorithm for this would therefore be a huge deal.
I hope that the proof will soon lead to practical implementations of the algorithm.
https://github.com/yinwang0/ydiff
This is also related to patch theory [2, 3, 4, 5, 6], a theory that seeks mathematise version control systems like, and to provide provably correct merging algorithms. Patch theory arose in the context of the DARCS system. [7] connects patch theory with homotopy type theory.
[1] https://ifl2014.github.io/submissions/ifl2014_submission_32....
[2] J. Dagit, Type-Correct Changes - A Safe Approach to Version Control Implementation.
[3] G. Sittampalam, Some properties of darcs patch theory.
[4] I. Lynagh, Camp Patch Theory.
[5] D. Roundy, Implementing the darcs patch formalism ... and verifying it.
[6] J. Jacobson, A Formalization Of Darcs Patch Theory Using Inverse Semigroups.
[7] C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.
[1] https://en.wikipedia.org/wiki/Clique_problem