The notion of communication complexity 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 fewer than n bits of communication.
This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.
Read more about Communication Complexity: Formal Definition, Randomized Communication Complexity, Quantum Communication Complexity, Nondeterministic Communication Complexity, Open Problems, Applications
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)