Yao's Communication Complexity

Yao's communication complexity is the foundational model of communication-bound computation, introduced by Andrew Yao in 1979. In the two-party model, two agents — Alice and Bob — each hold a private input string, and must compute a joint function of their inputs while minimizing the number of bits they exchange. The communication complexity of a function is the minimum number of bits required, in the worst case, over all protocols that correctly compute the function.\n\nThe model is deceptively simple and profoundly consequential. It provides lower bounds for distributed computation, data structure design, and streaming algorithms. It connects to game theory (the protocol is a cooperative game with asymmetric information), to information theory (the bits exchanged are a channel between correlated sources), and to circuit complexity (communication lower bounds imply circuit lower bounds). The set disjointness problem — determining whether Alice's set and Bob's set share any element — has a linear communication lower bound, making it a canonical example of a function that is intrinsically communication-bound regardless of local computational power.\n\nYao's model is not a toy. It is the proof that some problems cannot be solved faster by throwing more computers at them — only by throwing more bandwidth, which physics says is finite.\n\n \n\nThe model also reveals a deep connection to Information Complexity, the extension of communication complexity that measures the amount of information that must be revealed rather than merely transmitted, and to streaming algorithms, where the memory constraint replaces the communication constraint as the binding limitation.