Graph connectivity communication bound settled, with ChatGPT
Awaiting review
The takeaway
Zhijun Zhang (INSAIT) proves an optimal Ω(N log N) nondeterministic lower bound for graph connectivity, up from Raz–Spieker’s Ω(N log log N) of 1995. He also gives near-optimal randomized and optimal r-round bounds. The paper’s AI section says ChatGPT discovered the edge-colouring argument for Lemma 4.6 and produced a weaker first version of the randomized bound.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 26 October 2026
Your AI and this story
- GPT-6 Astra176 days after its cutoff
- Claude Opus 5.5115 days after its cutoff
- Gemini 4 Argon206 days after its cutoff
- Grok 4.7145 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 115 days before it.
Key facts
- Previously: the deterministic Θ(N log N) bound is due to Hajnal, Maass and Turán (STOC’88); optimal bounds were known only for 1-round (Sun–Woodruff 2015) and 2-round (Radhakrishnan–Reddy–Venkat, ITCS’26) protocols
- Method: bounds the size of 1-monochromatic rectangles via a new problem composing inner product with pointer chasing; extends to other graph properties
- AI statement (verbatim, excerpt): ‘Extensive interaction with ChatGPT was used to assist with exploring, formulating, and improving proof ideas for several lemmas in this paper. The tool materially affected Lemmas 4.6, 5.3 and C.2. In particular, 1. ChatGPT discovered the edge coloring argument for proving Lemma 4.6; 2. ChatGPT produced a preliminary version of the error-dependent randomized lower bound with worse Ω(log log(1/ε)) dependency on ε … The proof has been significantly simplified and improved by human authors … 3. ChatGPT suggested the use of Hölder’s inequality to optimize the lower order term in proving Lemma C.2.’
- Constant-error randomized complexity of connectivity remains open (the paper’s bound is optimal only for polynomially small ε)
What happened
In the two-party model, Alice and Bob each hold some edges of an N-vertex graph and want to know whether the union is connected. Sending a spanning forest costs O(N log N) bits, and that was known to be optimal for deterministic protocols since 1988. For nondeterministic protocols the best lower bound had been Ω(N log log N) since 1995. Zhijun Zhang closes that gap and nearly closes the randomized case.
His AI section is specific: ChatGPT “discovered the edge coloring argument” for one lemma, gave a weaker first version of the error-dependent randomized bound (which the author then strengthened), and suggested Hölder’s inequality for a lower-order term.
Why it matters
It settles a problem open for about four decades in a core area of complexity theory, with the AI contribution limited to named lemmas. The constant-error randomized case remains open.
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprint |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (arXiv PDF read)