Even after today’s retraction of quasi-polynomial time for graph isomorphism László Babai is famous for many things, and has made many seminal contributions to complexity theory. Last year he claimed that Graph Isomorphism (GI) is in quasi-polynomial time. Today Laci posted a retraction of this claim, conceding that the proof has a […]
The original letter explaining the retraction of the quasipolynomial claim can be found here. As explained in the blog post above and in the letter, the modified subexponential result is still very significant.