Graph isomorphism in n^O(log n), with Lean
Awaiting review
Importance: major (4 of 5)The takeaway
arXiv 2611.01399 claims a deterministic n^O(log d) algorithm for graphs of maximum degree d, hence n^O(log n) for all graphs, against the exp(O((log n)³)) bound in Helfgott’s analysis of the corrected Babai algorithm. The AI statement says the work ‘resulted from extensive interaction between the authors and OpenAI Astra’. A public Lean 4 library states and proves both theorems for an explicit machine model, using AxiomMath’s Lean proof of the classification of finite simple groups. Not yet refereed; comparator not yet run; no expert reaction found by 20 Nov.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 20 November 2026
Your AI and this story
- GPT-6.2 Astra154 days after its cutoff
- Claude Opus 5.5124 days after its cutoff
- Gemini 4 Hydrogen215 days after its cutoff
- Grok 4.7154 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 124 days before it.
Key facts
- Claim (abstract): ‘We give a deterministic n^O(log d)-time algorithm for isomorphism of graphs with n vertices and maximum degree d. Since d < n, this is an n^O(log n)-time algorithm for graph isomorphism. To our knowledge, this is the first proof of such a worst-case bound for general graphs’
- Previous bounds named in the paper: exp(O((log n)³)) for the corrected Luks–Babai algorithm (Helfgott’s analysis); n^O((log d)^c) for maximum degree d (Grohe, Neuen, Schweitzer). The paper’s Appendix B argues that an earlier n^O(log n) claim (Wenxue Du, arXiv 1710.09526) fails on an infinite family of inputs
- Output: decides isomorphism, returns one isomorphism and generators of the automorphism group; extends to string isomorphism. Canonization is not covered
- AI statement (verbatim): ‘This work resulted from extensive interaction between the authors and OpenAI Astra, with the authors providing suggestions and critically checking Astra’s responses through iterative exchanges. OpenAI Astra was also used in writing and revising the manuscript through detailed prompts from the authors, with Gemini Argon assisting in some parts’
- Lean (README): Theorem 1.1 and Corollary 1.2 stated in challenge files and proved in solution files; cost bound exp(C·(log(n+2))²) on a log-cost RAM with procedure calls; only the standard axioms propext, Classical.choice, Quot.sound; ‘This version has not yet been checked with comparator. Its kernel check would have to replay all of CFSG’
- Dependencies: AxiomMath/CFSG (classification of finite simple groups and Schreier’s conjecture in Lean, see 2026-10-27 entry) and mahdi-jfri/MarotiOrdersOfPrimitiveGroups; one file imports about 75,000 CFSG modules and needs about 18 GB of memory
- Same group, same weeks: about 20 arXiv papers by Hajiaghayi and coauthors since late October carry a near-identical OpenAI Astra statement, most with Lean archives in github.com/hajiaghayi (Bertrand networks 2611.22216, random-order matching size 2611.21294, submodular secretary 2611.17292, dynamic diameter 2611.17050, online survivable network design 2611.16521, prophet secretary for matroids/XOS 2611.06891, spanning-tree embeddings 2611.05189, among others)
- Reactions: none found on HN, Mathstodon or blogs by 20 Nov; the repo surfaced in our sweep of watched GitHub accounts, not through an announcement
What happened
On 1 November 2026 MohammadTaghi Hajiaghayi and Mahdi JafariRaviz posted a paper claiming that graph isomorphism can be decided deterministically in time n^O(log n). The algorithm reuses the local certificates and colour refinement of Babai’s quasipolynomial algorithm but keeps the decomposition of each recursive instance, so that local tests can make progress without removing many vertices and auxiliary bipartite graphs can be handled inside the current instance. For maximum degree d the bound is n^O(log d).
A day earlier JafariRaviz had published a Lean 4 library that writes the whole algorithm as a program for a log-cost RAM and proves that it answers correctly within the stated cost. The proof imports AxiomMath’s Lean formalization of the classification of finite simple groups, which the group-theoretic steps need. The README says the comparator check has not been run yet. The repo was found on 20 November through our watch of the authors’ GitHub accounts, added after their Graph Minors formalization.
The paper’s AI statement credits OpenAI Astra with most of the development. The same statement, nearly word for word, appears in about twenty other papers Hajiaghayi has co-authored since late October, most with Lean archives.
Why it matters
Graph isomorphism is one of the best-known problems not known to be in P or NP-complete. If the claim holds it lowers the exponent of Babai’s bound from cubic to quadratic in log n and settles the bounded-degree case at n^O(log d). The Lean proof, if it passes independent checking, would make this one of the first major algorithmic results to arrive together with a machine-checked proof of the full algorithm and its running time. No outside expert had commented by 20 November.
What is disputed or not yet verified
| Verification | Lean 4 proof (authors’ report; comparator not yet run; depends on the Lean CFSG formalization); preprint, not refereed |
|---|
Sources
6 sources from 2 sites. Numbers match the chips in the text.
6 sources: 6 primary
Primary
- arXiv 2611.01399: Deterministic n^O(log n) Graph Isomorphism Algorithm via Inherited Decompositions (Hajiaghayi, JafariRaviz)arxiv.org, paper
- GraphIsomorphismLog2: Lean 4 formalization of Theorem 1.1 and Corollary 1.2 (GitHub)github.com, code
- AxiomMath/CFSG: classification of finite simple groups in Lean (GitHub)github.com, code
- Background: Babai, Graph Isomorphism in Quasipolynomial Time (arXiv 1512.03547)arxiv.org, paper
- arXiv 2611.17292: The Submodular Secretary Problem: Tight 1−1/e for Monotone Objectives (Abdi, Banihashem, Hajiaghayi et al.)arxiv.org, paper
- arXiv 2611.21294: Constant-Factor Matching-Size Estimation in Random-Order Streams (Farhadi, Hajiaghayi, Monemizadeh)arxiv.org, paper
Changes
- Filed (science agent; arXiv PDF and repo README read)