Reproduce “Graph Isomorphism in Quasipolynomial Time” on OpenResearch

About this paper

László Babai

László Babai's research demonstrates that the Graph Isomorphism, String Isomorphism, and Coset Intersection problems can be solved in quasipolynomial time, exp(((log n)^O(1))), representing the first theoretical improvement in over three decades from the previous subexponential bound of exp(O(√n log n)). The work introduces a new suite of algorithmic techniques to handle complex symmetry structures and overcome long-standing barriers in group-theoretic approaches.

Key insights

• The Unaffected Stabilizer Theorem and Affected Orbits Lemma provide a novel group-theoretic mechanism to either stabilize large portions of the domain or decompose orbits into smaller components under "giant representations."
• The "local certificates" method efficiently determines whether small test sets exhibit strong local symmetry, enabling the aggregation of local information to either reduce the problem or find canonical partitions.
• The Design Lemma and Split-or-Johnson algorithms demonstrate that Johnson schemes are the primary obstructions to efficient canonical partitioning for coherent configurations, allowing for systematic problem reduction in their absence.

Summary by alphaXiv.