Communication Complexity
Communication Complexity is the study of the information theoretic
requirements for computations whose input is distributed over several
cooperating agents. It is is a central tool for obtaining lower bounds
in several areas, especially in circuit complexity and computation
using bounded space. With the advent of quantum computation, a model
of quantum communication has also been studied. Several communication
models have been defined to handle different applications, and deep
combinatorial, algebraic, probabilistic and geometric techniques play
an important role in analysing these. Recently, deep combinatorial,
algebraic and geometric techniques have been employed to understand
communication problems,and there is emerging a set of powerful
techniques that bring hitherto inaccessible problems tantalisingly
close to resolution. Interestingly, these techniques apply to both the
classical and the quantum models.