Graph Isomorphism (Gl)Problem input:two undirected graphs G and H output:G≈H? p n 6) vertices 8 7 ^b Gl is in NP,but is NOT known to be in P or NPC trivial algorithm:O(n!)time Babai-Luks'83:20(vmlogn)time Babai 2015:a quasi-polynomial time algorithm! npolylog(n)=2polylog(n) Graph Isomorphism (GI) Problem ? • GI is in NP, but is NOT known to be in P or NPC • trivial algorithm: O(n!) time • Babai-Luks ’83: time n vertices Babai 2015: a quasi-polynomial time algorithm! npolylog(n) = 2polylog(n) 2O( pn log n) ⇠ = input: two undirected graphs G and H output: G ⇠ = H ?