News for hackers. Stuff that matters.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by ThePhysicist on Wednesday November 04, 2015 @02:03PM (#10508739)
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.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by mafribe on Thursday November 05, 2015 @06:22AM (#10512750)
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.

[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.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by est on Thursday November 05, 2015 @12:11AM (#10511737)
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by ThePhysicist on Thursday November 05, 2015 @05:09AM (#10512565)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by espes on Wednesday November 04, 2015 @02:48PM (#10509103)
Why is general graph isomorphism needed for that?
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by ThePhysicist on Thursday November 05, 2015 @05:07AM (#10512561)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by espes on Thursday November 05, 2015 @08:23AM (#10513123)
But it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by ThePhysicist on Thursday November 05, 2015 @11:02AM (#10514055)
ASTs are DAGs indeed, but as soon as you add semantic information to the mix the graph usually becomes cyclic.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by caf on Thursday November 05, 2015 @07:57AM (#10513013)
Tree Isomorphism is a much easier problem than general Graph Isomorphism.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by Ar-Curunir on Wednesday November 04, 2015 @03:47PM (#10509587)
Most real life instances of Graph Isomorphism are easily solved in polynomial time though...
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by johncolanduoni on Wednesday November 04, 2015 @03:52PM (#10509642)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by bmh100 on Wednesday November 04, 2015 @04:42PM (#10509994)
Is this the sort of technology that could theoretically enable reasonably good, automated conversion between programming languages?
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by obastani on Thursday November 05, 2015 @09:41AM (#10513527)
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.).
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by ThePhysicist on Thursday November 05, 2015 @05:04AM (#10512550)
I would say it's part of it but by far the only thing that you'd need to solve for this, in my opinion.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by gone35 on Wednesday November 04, 2015 @10:59AM (#10507439)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by yk on Wednesday November 04, 2015 @02:48PM (#10509096)
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.)
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by davidamarquis on Wednesday November 04, 2015 @06:10PM (#10510484)
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.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by bmh100 on Wednesday November 04, 2015 @04:45PM (#10510017)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by gone35 on Thursday November 12, 2015 @12:22PM (#10554518)
Sorry not my field! But I would first give NAUTY[1] a try before trying more exotic, structure-exploiting stuff.

[1] http://www3.cs.stonybrook.edu/~algorith/implement/nauty/impl...

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by fitzwatermellow on Wednesday November 04, 2015 @01:05PM (#10508363)
Yes, it's a rarity indeed!
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by harperlee on Wednesday November 04, 2015 @10:23AM (#10507162)
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!
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by Someone on Wednesday November 04, 2015 @11:01AM (#10507454)
What part do you have problems with? Graph isomorphism or quasi-polynomial?

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.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by JD557 on Wednesday November 04, 2015 @10:55AM (#10507405)
Disclaimer: I don't know much about the subject, but I'll try to help.

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).

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by tinco on Thursday November 05, 2015 @07:13AM (#10512880)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by oofabz on Wednesday November 04, 2015 @02:54PM (#10509147)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by johncolanduoni on Wednesday November 04, 2015 @03:47PM (#10509583)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by leecarraher on Wednesday November 04, 2015 @11:02AM (#10507457)
woozers, really excited to see this. hope videolectures.net picks up the presentation soon afterward.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by andrewla on Wednesday November 04, 2015 @09:40AM (#10506834)
Original title "Quasi-Polynomial Algorithm for Graphic Isomorphism Proposed" should be "Graph" instead of "Graphic"
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by johncolanduoni on Wednesday November 04, 2015 @09:42AM (#10506848)
You know you've been up too long when you write graph as graphic, even though you've written a paper on graph theory XD.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by duaneb on Wednesday November 04, 2015 @10:41AM (#10507284)
Ahh yea that makes a lot more sense
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by dang on Wednesday November 04, 2015 @01:31PM (#10508511)
Yes. Fixed.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by jsprogrammer on Wednesday November 04, 2015 @02:14PM (#10508817)
...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.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by dang on Wednesday November 04, 2015 @08:12PM (#10510943)
That seems a bit nitpicky. The post doesn't contain a proposal either.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by jsprogrammer on Thursday November 05, 2015 @01:49AM (#10512001)
I agree. I only used the word because it was the apparent original title (according to the person you responded to).

Possible Quasi-Polynomial Graph Isomorphism Problem Algorithm Upcoming?

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by amelius on Thursday November 05, 2015 @05:42AM (#10512643)
I wonder if bits of the proof could be used for other graph problems. For instance the "clique problem" [1], which is NP complete.

[1] https://en.wikipedia.org/wiki/Clique_problem

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by eximius on Wednesday November 04, 2015 @11:23AM (#10507606)
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.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by JadeNB on Wednesday November 04, 2015 @12:23PM (#10508047)
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).
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by eximius on Wednesday November 04, 2015 @09:29PM (#10511248)
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.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by JadeNB on Wednesday November 04, 2015 @09:56PM (#10511361)
> 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.)

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by 314 on Wednesday November 04, 2015 @01:07PM (#10508372)
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.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by eximius on Wednesday November 04, 2015 @09:26PM (#10511237)
Don't understand the downvotes guys... not cool.