.png)
The area of communication complexity studies measures communication as computational resource—a mathematical abstraction that encompasses all the problems with communication bottleneck. The basic model of communication complexity deals with two parties, namely Alice and Bob. Their task is to compute a function on input which is distributed among them. For doing so, they communicate between each other adhering to a set of rules which they agree upon a priori, and what we measure is the number of bits they need to communicate in order to compute the function. This problem, and many of its variants, appear frequently in practice in many guises and in different levels of
abstractions—in network protocols, in algorithms for NP-hard problems, in lower bounds for boolean circuits.
In this course, we will discuss the classical results in communication complexity and also cover the recent developments and important open problems. We will discuss different models of communication complexity—deterministic, nondeterministic, asymmetric, randomized, and multiparty—and their inter-relationship. We will mostly be interested in showing combinatorial, algebraic and information theoretic techniques for showing communication complexity lower bounds, but we also consider some applications of this theory.
References