TOPICS
Search

Communication Complexity


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 x, Bob knows y, and their communication must determine f(x,y). 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 n-vertex graph is connected has nondeterministic communication complexity Theta(nlnn) when Alice and Bob hold disjoint sets of its edges, where Theta 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 UPP^(cc) of functions having polylogarithmic complexity in this model is not closed under intersection. Their explicit example has complexity O(lnn), whereas the conjunction of two independent copies requires Omega(sqrt(n)) bits. Here O and Omega denote big-O notation and big-omega notation, and n is the number of input bits held by each party.


See also

Computational Complexity, Complexity Theory

Explore with Wolfram|Alpha

References

Bun, M. and Juvekar, M. "UPP^(cc) Is Not Closed Under Intersection." 27 Oct 2026. https://arxiv.org/abs/2610.37634.Kushilevitz, E. and Nisan, N. Communication Complexity. Cambridge, England: Cambridge University Press, 1997. https://doi.org/10.1017/CBO9780511574948.Zhang, Z. "Settling Nondeterministic Communication Complexity of Graph Connectivity." 23 Oct 2026. https://arxiv.org/abs/2610.32346.

Cite this as:

Weisstein, Eric W. "Communication Complexity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CommunicationComplexity.html

Subject classifications