PaperfootJoin free
arXiv

Proof settles communication limit for graph connectivity

A mathematical proof establishes an optimal lower bound on nondeterministic communication for graph connectivity, resolving a problem that remained open for decades.

Paper by Zhijun Zhang
A connected light blue network with black branches sits beside a large cluster of dark blue-green rectangles and a smaller gray cluster.
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

In a preprint, the authors proved an optimal lower bound—a limit no protocol can beat—on the nondeterministic communication complexity of graph connectivity, the amount of data separate computers must exchange to determine whether a network is connected. A simple procedure that shares a spanning forest solves the problem on an N-vertex network, but whether nondeterministic or randomized methods could use less communication remained unresolved for decades. The authors proved that nondeterministic protocols require communication proportional to N times the logarithm of N, matching the simple procedure and improving on the best prior bound by Raz and Spieker. They established the limit by bounding the maximum size of mathematical structures called 1-monochromatic rectangles. Generalizing the technique to randomized protocols yielded optimal bounds for small error probabilities and for any constant number of communication rounds.

Why it matters

The mathematical proof resolves a question in communication complexity that had stood open since 1986. The authors report that the lower bounds can be extended to other fundamental graph properties, and also imply the optimality of known query and streaming algorithms for related problems.

Caveats

The findings are theoretical proofs of communication limits rather than tests of real computing networks. The paper is also a preprint that has not yet been peer-reviewed.

In this paper

nondeterministic communication complexity of graph connectivity

What it shows

The nondeterministic communication complexity of graph connectivity has an optimal Ω(Nlog N) lower bound on N-vertex graphs.

We settle the nondeterministic communication complexity of graph connectivity by proving an optimal Ω(Nlog N) lower bound.

Abstract

Any r-round protocol with constant error probability requires Ω(N/r · log N) communication, which is optimal for every constant r.

For constant error probability, we also prove that any r-round protocol requires Ω(N/r · log N) communication, which is optimal for every constant r.

Abstract

Quoted word for word from the abstract on arXiv.

The paper

Settling Nondeterministic Communication Complexity of Graph Connectivity

Zhijun Zhang

arXiv, Oct 23, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.32346

arXiv:2610.32346v1 in cs.CC

AbstractPDFHTML

Cite as BibTeX
@misc{zhang2026settling,
  title = {Settling Nondeterministic Communication Complexity of Graph Connectivity},
  author = {Zhang, Zhijun},
  year = {2026},
  eprint = {2610.32346},
  archivePrefix = {arXiv},
  primaryClass = {cs.CC},
  doi = {10.48550/arxiv.2610.32346},
  url = {https://arxiv.org/abs/2610.32346}
}

Related