Quasi-Polynomial Algorithm for Graph Isomorphism
scottaaronson.com
scottaaronson.com
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.
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.
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...
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.
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.
Possible Quasi-Polynomial Graph Isomorphism Problem Algorithm Upcoming?
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.)