Graph Isomorphism in Quasipolynomial Time.¶
Babai, L. (2016). Graph Isomorphism in Quasipolynomial Time. Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 684-697.
Cited by¶
3 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Canonical Form
- The presence or absence of a canonical form is itself a structural property of the domain-and-relation pair, and some problems — graph-isomorphism canonical labeling, equivalence of context-free grammars — lack known efficient canonical forms, and the absence is the complexity barrier.
This sourceEstablishes the difficulty of canonical labeling for graph isomorphism — the absence of a known efficient canonical form as the complexity barrier.
- The presence or absence of a canonical form is itself a structural property of the domain-and-relation pair, and some problems — graph-isomorphism canonical labeling, equivalence of context-free grammars — lack known efficient canonical forms, and the absence is the complexity barrier.
- Isomorphism
- … science: the graph isomorphism problem (decide whether two graphs $G_1$ and $G_2$ are isomorphic) is in NP but not known to be in P or NP-complete, and Babai's 2015 announcement of a quasi-polynomial-time algorithm — running in time $\exp((\log n)^{O(1)})$ — is the major recent advance on its complexity status.
This source(Major recent advance on the algorithmic complexity of graph isomorphism: a quasi-polynomial-time algorithm running in $\exp((\log n)^{O(1)})$, substantially improving on the previous best $\exp(O(\sqrt{n \log n}))$ bound; the result places graph isomorphism in a complexity class strictly between P and NP-complete under widely-believed conjectures, and supports the hypothesis that the graph-isomorphism problem is in the GI complexity class as a candidate intermediate class.)
- … science: the graph isomorphism problem (decide whether two graphs $G_1$ and $G_2$ are isomorphic) is in NP but not known to be in P or NP-complete, and Babai's 2015 announcement of a quasi-polynomial-time algorithm — running in time $\exp((\log n)^{O(1)})$ — is the major recent advance on its complexity status.
- Symmetry
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:3ee28c746843 · see in the full table