ECCC-Report TR03-075https://eccc.weizmann.ac.il/report/2003/075Comments and Revisions published for TR03-075en-usThu, 16 Oct 2003 14:55:02 +0200
Paper TR03-075
| A tutorial on the Deterministic two-party Communication Complexity |
Agostino Capponi
https://eccc.weizmann.ac.il/report/2003/075Communication 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.
Thu, 16 Oct 2003 14:55:02 +0200https://eccc.weizmann.ac.il/report/2003/075