Innovative Algorithm for Solving Graph Isomorphism

A recent breakthrough for solving graph isomorphism has solved one of the mysteries in complexity theory and computer science. This innovative algorithm appears to be significantly more efficient than previous algorithms.

The concept of a "graph” refers to a network of nodes with edges connecting some of the nodes. Graph isomorphism asks when two graphs are really the same graph in disguise because there’s a one-to-one correspondence (an “isomorphism”) between their nodes that preserves the ways the nodes are connected. Hard to solve because graphs can be made to look very different just by moving their nodes around.

The innovation is a “quasi-polynomial-time” algorithm - which means that for a graph with nnodes, the algorithm’s running time is comparable to n raised not to a constant power (as in a polynomial) but to a power that grows very slowly.

I predict this innovation will have a big future impact with new system architectures.

Download paper here.