The communication complexity of a function f(x, y) measures the number of bits that two players, one who knows x and the other who knows y, must exchange to det

This book deals mostly with impossibility results - lower bounds on what can be accomplished by algorithms. However, the perspective is unapologetically that of

We survey several techniques for proving lower bounds in Boolean, algebraic, and communication complexity based on certain linear algebraic approaches. The comm

Surveys the mathematical theory and applications such as computer networks, VLSI circuits, and data structures.

The communication complexity of two-party protocols is an only 15 years old complexity measure, but it is already considered to be one of the fundamen tal compl