Key Concepts

Babai's quasi-polynomial time isomorphism test

• Generally, algos with runtime of form $n^{\text{polylog}(k)}$ where $k$ is graph parameter such as maximum degree
• Babai: $n^{\text{polylog}(n)}$ := $n^{(\text{log } n)^{O(1)}}$
• Improvement over: $2^{O(\sqrt{n \text{ log }n})}$ (due to Luks)

Weisfeiler-Leman Algorithm

Unfamiliar Terms

• []