---
id: "2026-10-23-graph-connectivity-nondeterministic-communication-complexity-chatgpt"
url: "https://postcutoff.com/e/2026-10-23-graph-connectivity-nondeterministic-communication-complexity-chatgpt/"
as_of: "2026-10-30T13:42:00+01:00"
date: "2026-10-23"
date_precision: day
category: science
importance: 3
confidence: medium
status: [Awaiting review]
verification: Preprint only
sources: 1
editor: human editor
human_review: null
version: "2026-10-27"
---

As of: 2026-10-30 13:42 CET.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-10-23-graph-connectivity-nondeterministic-communication-complexity-chatgpt/

# Graph connectivity communication bound settled, with ChatGPT

Full title: Nondeterministic communication complexity of graph connectivity settled at Θ(N log N), open since 1986; ChatGPT found a key lemma's argument

arXiv 2610.32346 (23 Oct 2026): "Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]." The paper proves the optimal Ω(N log N) nondeterministic lower bound (previous best Ω(N log log N), Raz–Spieker 1995). It also proves Ω(N·log(min(1/ε, N))) for randomized protocols with error ε, optimal for polynomially small ε, and Ω(N/r·log N) for r-round protocols. The "AI Methodology" section says ChatGPT materially affected Lemmas 4.6, 5.3 and C.2.

## 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

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 176 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 115 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 206 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 145 days after its cutoff

## Sources

1. [arXiv 2610.32346: Settling Nondeterministic Communication Complexity of Graph Connectivity (Zhijun Zhang)](https://arxiv.org/abs/2610.32346) (arxiv.org, paper)

## Changes

- 2026-10-26 (filed): Created (arXiv PDF read)

## Related

- 2026-10-26: [AI-assisted results in the 26 Oct 2026 sweep](https://postcutoff.com/e/2026-10-26-ai-assisted-results-october-26-listing/index.md)