Algorithms for Smart World Technologies

Chapter 3Communication Complexity

Communication complexity is a subfield of computational complexity theory that focuses on quantifying the amount of communication required between two or more parties to jointly compute a function. In the classical two-party model, two players—Alice and Bob—are each given part of the input, typically in the form of -bit strings and . Their goal is to compute a function that depends on both inputs while exchanging as little information as possible. This model was introduced by Andrew Yao in 1979 to analyze the cost of distributed computation across multiple machines. Since then, it has found wide-ranging applications in circuit complexity, data structures, streaming algorithms, distributed systems, and cryptography. The central question it addresses is: Given and held by Alice and Bob, how many bits must they communicate to determine the value of