Type and Content

Communication Complexity measures the amount of information that has to be transferred between different agents in order to perform specific computational tasks, like identification of individuals, comparing strings, computing a Boolean function, or performing an electronic auction. Protocols may be deterministic or randomized using a certain number of random bits that may be given privately to each agent or known publicly.

In particular, so called interactive protocols and probabilistically checkable proofs have recently turned out to be a good model for a variety of computational tasks. The seminar will give an introduction to these topics.

The participants will present recent research work done in this area. As a basic text we will use the monograph of

• Nisan, Kushilevitz, Communication Complexity, Cambridge University Press, 1997

and recent Journal and Conference publications of various authors.

Lecture