Graph Isomorphism in Quasipolynomial Time.¶
Babai, L. (2015/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¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Not recorded. Neither this nor any other of the 3 citations of this work carries a recorded support check.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:3ee28c746843 · see in the full table