A Fast Graph Isomorphism Algorithm
While we wait for Laci 
László Babai just gave his first talk on his new graph isomorphism (GI) algorithm. The photo was taken at the talk and posted by several people.
Today we want to discuss his talk, but
But we were not there. Nor were we able to send a GLL representative there to hear the talk. There are twitter feeds here and here. The former, by Gabriel Gaster, gives a running textual description, but otherwise we are still pretty in the dark as to the details of the algorithm.
Or are we?
A Fast Algorithm
There is old trick essentially due, I believe first, to Leonid Levin. This allows us to give a graph isomorphism algorithm that works almost in quasi-polynomial time—without seeing Laci’s algorithm. While we are in the dark I thought you might enjoy it.
Theorem: There is a concrete algorithm
that runs in time
and decides graph isomorphism correctly.
Here 
Then the algorithm is:
Let
and
be
vertex graphs. Run all Turing Machines of size less that
is one of the outputs. Check whether
Call this algorithm 
So we can start running the algorithm without the details. Of course there are two problems. The first is that the running time here is huge—its a galactic algorithm. Second, its correctness relies on Laci’s theorem, and also we do not know when it starts to work. So it really is useless.
But it does show the power of Levin’s old idea.
Open Problems
Of course we must wait for Laci’s paper, which we hear is due out soon. And that is the key.
Where you wrote \log(n)^{\log*(n)}, I believe you meant to write exp(\log(n)^{\log*(n)})
Noah
Thanks, and of course.
dick
the statement “without seeing his algorithm” is a bit problematic! amusing as always, but whats the fine print—your “theorem” assumes his proof has some quasipolynomial Dtime function right? how about a human readable interpretation? “for any algorithm that runs in time f(n), there is another one that runs ‘slightly’ faster, but is galactic,” to borrow one of your own terms…?
Jeremy Kun wrote a blog post giving an overview of the first talk at
http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/
Sorry, but I understand nothing about the {}“problem” of string
isomorphism. The definition of graph isomorphism is: $G=P^{-1}G^{\prime}P$,
where $G$ and $G^{\prime}$ are adjacent matrices of given graphs;
$P$ is permitation matrix. So, we can imagine the same definition
for string isomorphism, where $G$ and $G^{\prime}$ are strings (vectors).
For example, a string {}“adcb” and a string {}“badc” are isomorphic.
But, there is significant difference in the definitions: adjacent
matrix is 2D (two dimension) structure, string (vector) is 1D structure:
we know how to sort 1D structure, but we do not know how to sort a
matrix.
Theorem: we can sort vector for polynomial time.
Proof: See buble sort in wiki.
The strings {}“adcb” and {}“badc” have trivial canonical form:
{}“abcd”, similar form is not obvious for graphs.
I only want to say that in contrast with graph isomorphism problem,
the string isomorphism {}“problem” is trivial problem.
A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/
Drs. Reagan and Lipton, your commentary is very appreciated, it is all well and good, but maybe you could also invite other experts, like C. BERKHOLZ or MARTIN GROHE to comment.
Martin Grohe is welcome to reply—we were last seen playing soccer—meanwhile we thank commenter “mt2mt2” for posting a link to details by Jeremy Kun.
http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4
I think a post on Eugene Luks’ algorithm for group isomorphism would be nice.
I am not a computer scientist, and have not thought about graph isomorphism before, but thinking about it naively it does not seem to be a hard problem. Given graphs G and H there are obvious checks on their degree sequences that can immediately be evidence that they are not isomorphic. Then one can look at degree sequences of the powers of these graphs G^k and H^k for k = 2, 3, 4… If those types of checks all pass, then one can look at the spectrum of the adjacency matrices of G and H (and perhaps their powers as well). For if the graphs are isomorphic then the spectrums of their adjacency matrices are identical. Eigenvalue computation is a O(N^3) problem. It would have to be a pretty weird conspiracy to have two graphs which are not isomorphic to have the same spectrum (or the spectrum of the powers of those graphs).
slt,
“Weird conspiracies” happen all the time in math/computer science :).
I agree with that in general, but for this particular problem can you give examples of families of pairs of graphs which are non-isomorphic but have the same spectrum? Maybe that will shed some light as to why this is a difficult problem.
I found a paper that goes into this topic:
https://cs.anu.edu.au/people/Brendan.McKay/papers/GodsilMcKayCospectral.pdf
The “conspiracy” is not particularly deep. Very interesting stuff.
Example 2.3 (a) in the above paper is interesting. There are two non-isomorphic graphs on 9-vertices (call them G and H) that have the same spectrum and the same degree sequence. However the degree sequence of G^2 and H^2 is already different. Maybe looking at the degree sequence of a high power of the graphs is a better discriminant than looking at their spectrum.
I bet someone has found a pair of graphs that are non-isomorphic but have the same degree sequence for all powers. Kind of like the situation with the Fermat primality test and Carmichael numbers. Alright I will stop polluting your blog.
There is a lot of non-isomorphic cospectral graphs (http://mathworld.wolfram.com/CospectralGraphs.html).
P = NP problem (proven)
P=NP, in the factorization of all odd number.
See: http://www.ijma.info Vol 6 (9) 2015
Again, I see [video src="http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4" /], but I do not understand why GI may be reduced to string isomorphism?
The algorithm for Isomorphism of the order of the cube of the number of edges is here guys!
http://vixra.org/pdf/1512.0322v1.pdf
Please note that the above referenced Isomorphism condition:
http://vixra.org/pdf/1512.0322v1.pdf
is applicable to strongly regular graphs. For other graphs it is not directly applicable and in that case one needs to arrange first the vertices in nonincreasing degree sequence and then label the vertices with labels {1, 2, …., p} and one need to apply transpositions among vertices with same degree for conclusively implying nonisomorphism when we cannot identify next edge labels without disturbing earlier identified edge labels.
DPM
Please refer to Isomorphism checking algorithm at:
http://vixra.org/pdf/1512.0322v2.pdf
Thank you, DPM