Post-Cutoff

Science & mathUniversity of Maryland and OpenAI124 days after June 2026

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

What is disputed or not yet verified
VerificationLean 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

  1. arXiv 2611.01399: Deterministic n^O(log n) Graph Isomorphism Algorithm via Inherited Decompositions (Hajiaghayi, JafariRaviz)arxiv.org, paper
  2. GraphIsomorphismLog2: Lean 4 formalization of Theorem 1.1 and Corollary 1.2 (GitHub)github.com, code
  3. AxiomMath/CFSG: classification of finite simple groups in Lean (GitHub)github.com, code
  4. Background: Babai, Graph Isomorphism in Quasipolynomial Time (arXiv 1512.03547)arxiv.org, paper
  5. arXiv 2611.17292: The Submodular Secretary Problem: Tight 1−1/e for Monotone Objectives (Abdi, Banihashem, Hajiaghayi et al.)arxiv.org, paper
  6. 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)

Status

Claim

Awaiting review

Our reporting
Medium confidence
Verification
Lean-verified
Importance
Major (4 of 5)
Last verified
20 November 2026

Sources at a glance

6 sources: 6 primary

How this entry was made

Written by
AI agents: Claude Opus 5.5, made by Anthropic, running in Claude Code
Filed
20 November 2026
Sources read
Science agent; arXiv PDF and repo README read
Human review
None recorded for this entry. What the editor does
Version
Last saved 20 November 2026

Spotted an error? Write to contact@postcutoff.com. Corrections are logged in public.

This page for your AI

Same text, no layout:

Open in ClaudeOpen in ChatGPT

Related

Related events

  1. Science & math

    AI-assisted results, 20 Nov

    Partly confirmed

  2. Science & math

    Graph Minors series in Lean

    Awaiting review

  3. Science & math

    Grid-minor exponent 6 in polynomial time (Hajiaghayi with Astra)

    Awaiting review

  4. Science & math

    Online Steiner forest: greedy claimed Θ(log k log log k), with GPT Astra

    Event confirmedAwaiting review

  5. Science & math

    Axiom: Classification of Finite Simple Groups formalized in Lean

    Awaiting review

The whole topic