This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this week, and the abstracts are here. I'm not an expert in this field (for instance, I had to look up what polylog means), but clearly this is a very significant result. Babai is a giant in this field, so let's assume for now that the claimed result is correct.

(1) What are some implications of this result in complexity theory?

For example: This problem is NP, but is not known to be NP-complete. If it were NP complete, and if the algorithm were polynomial time, then we'd know P = NP and that would be huge. Does this new result give us any insight into the class of problems that are NP but not known to be NP complete? Does it prove that Graph Isomorphism is not in some other class of problems (e.g. does anyone study the class of exponential but not quasi-polynomial time problems)?

(2) Are there other important problems that reduce to the graph isomorphism problem that are now known to be solvable in quasi-polynomial?

Babai's abstract mentions the Coset Intersection problem and the String Intersection problem. I can guess what those are from the name. Are there other well-studied problems that reduce to graph isomorphism?

(3) How far is quasi-polynomial from polynomial?

Based on the linked thread above, polylog generally means $O(\log(n)^k)$ in complexity theory. ~~ If so, then exp[\log(n)^k]) = exp[k]*n, which doesn't look all that much like polynomial time, unless you can bound $k$ by a constant that doesn't depend on $n$. But perhaps I'm misunderstanding the whole story, in which case I'd love to be set straight.~~ What would be the next step to getting the bound lower, from the perspective of complexity theory?

Obviously, the proof hasn't appeared in print yet, so I'm not asking if the proof can somehow be made polynomial instead of quasi-polynomial, and I'm definitely not asking if it's correct. I'm asking what it implies if it's correct, and how much it changes the current playing field for complexity theory.

EDIT (based on the comments):

(4) Is there any known implication of this new result in Quantum Computing?

extremelyslowly. My understanding is that functions this slow do not appear in computer science but do sometimes appear in, say, analytic number theory. $\endgroup$ – Theo Johnson-Freyd Nov 13 '15 at 5:15inverse Ackermann function, which is the optimal amortized time complexity for the union-find problem in computer science: en.wikipedia.org/wiki/Disjoint-set_data_structure $\endgroup$ – Adam P. Goucher Nov 13 '15 at 11:349more comments