Communication complexity measures the number of bits that parties with separately held inputs must exchange to compute a function of their
combined input. In the two-party model, Alice knows 
, Bob knows 
, and their communication must determine 
. Local computation is unrestricted. Deterministic, randomized,
and nondeterministic protocols impose different requirements on the communication
(Kushilevitz and Nisan 1997).
A nondeterministic protocol accepts a pair of inputs when at least one accepting communication transcript is consistent with them. Zhang (2026) proved that deciding
whether an 
-vertex
graph is connected has
nondeterministic communication complexity 
when Alice and Bob hold disjoint sets of its edges, where 
denotes big-Theta notation.
The upper bound communicates a spanning tree, and
the lower bound matches its order of growth. Zhang (2026) credits ChatGPT with a
key edge coloring lemma and an optimization using
Hölder's inequality.
