The notion of communication complexity (CC) was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob). Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to
compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of
communication required for such distributed computations. Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with less than n bits of communication.
Reference: Communication complexity By Eyal Kushilevitz, Noam Nisan
(We will try to cover the first chapter of this book.)
