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.