Questions about the amount of communication required to compute a function whose input is distributed between two or more parties
Communication complexity is a model of computation invented by Yao. In this model, two or more parties are cooperating in computing a function whose input is distributed among the parties. Their goal is to minimize the number of bits communicated.
Interesting on its own, communication complexity also has many applications to other parts of complexity theory. Most such applications consist of applying communication complexity lower bounds.
