Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-075 | 7th September 2003 00:00

A tutorial on the Deterministic two-party Communication Complexity


Authors: Agostino Capponi
Publication: 16th October 2003 14:55
Downloads: 3646


Communication complexity is concerned with the question: how much information do the participants of a communication system need to exchange in order to perform certain tasks? The minimum number of bits that must be communicated is the deterministic communication complexity of $f$. This complexity measure was introduced by Yao \cite{1} to focus attention on the cost of information transfer associated with a given distributed computation. Subsequently the model has been studied for its own sake as an interesting abstract model of computation. Here we present a tutorial on the two-party deterministic communication complexity. First we illustrate the basic algebraic and combinatorial tools used in this theory. Then we discuss the communication complexity of specific functions and some of the many applications that the theory of communication complexity has. We also dedicate one paragraph to briefly mention some variants of the basic model of the deterministic two-party
communication complexity.

ISSN 1433-8092 | Imprint