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.
In the unbounded-error randomized model, the protocol need only succeed with probability strictly greater than one half on every input, with no fixed positive advantage.
This complexity is characterized by the sign rank of
the sign matrix of the function.
Bun and Juvekar (2026) proved that the class of functions having polylogarithmic
complexity in this model is not closed under intersection. Their explicit example
has complexity
,
whereas the conjunction of two independent copies requires
bits. Here
and
denote big-O notation
and big-omega notation, and
is the number of input bits held by each party.