Communication Complexity

Core Idea

Communication complexity, introduced by Yao (1979), studies the minimum number of bits two parties (Alice and Bob) must exchange to compute a function f(x, y) when Alice holds x and Bob holds y. The equality function (is x = y?) requires Omega(n) deterministic bits but only O(1) randomized bits (with error). The set disjointness function requires Omega(n) bits even with randomization — a foundational result that implies streaming space lower bounds for frequency moments, distinct counting, and many other problems. Communication complexity provides the primary tool for proving lower bounds in data streams, distributed computing, and circuit complexity, making it one of the most broadly applicable areas of computational complexity.

Explainer

Communication complexity provides a clean mathematical model for understanding the fundamental limits of computation when information is distributed. Alice holds input x, Bob holds input y, and they want to compute f(x, y) by exchanging messages. The communication complexity of f is the minimum number of bits they must exchange in the worst case. Despite the model's simplicity, it captures deep computational phenomena and provides the primary tool for proving lower bounds across computer science.

The equality function illustrates the power of randomization in this model. Deterministically, Alice and Bob must exchange Omega(n) bits — any protocol with fewer bits conflates two inputs for Alice that Bob cannot distinguish. But with shared randomness, they can use fingerprinting: agree on a random hash function, each compute and compare fingerprints. With O(log n) bits exchanged and error probability 1/n per round, a constant number of rounds gives constant error probability with O(log n) total communication. The gap from n to log n demonstrates that randomization provides an exponential advantage for some communication problems.

Set disjointness is the most important hard problem in communication complexity. Alice and Bob hold subsets A, B of {1,...,n} and must determine whether A and B are disjoint. Even with randomization and unbounded computation, Omega(n) bits must be exchanged. The proof, due to Kalyanasundaram and Schnitger (and simplified by Razborov), uses information-theoretic arguments showing that any protocol must reveal Omega(n) bits of information about the inputs. This seemingly narrow result has enormous consequences: almost every streaming lower bound reduces from set disjointness. If a streaming algorithm uses s bits of space, it implicitly defines a communication protocol where Alice sends the s-bit memory state after processing her portion of the stream.

The broader significance of communication complexity extends to circuit complexity (Karchmer-Wigderson games relate circuit depth to communication complexity), data structure lower bounds (cell-probe lower bounds reduce to communication problems), and distributed computing (where communication is the actual bottleneck, not an abstraction). The information complexity framework, which measures the information revealed by the communication protocol rather than just the number of bits, provides even tighter lower bounds and connects to rate-distortion theory from information theory. This rich web of connections makes communication complexity one of the most productive areas in theoretical computer science.