Course Description

This is the home page of the Communications Complexity course. Communication Complexity considers problems where the input is distributed amongst two or more parties who must work together to produce some output. In communication complexity, we are primarily interested in how much communication must occur for the parties to correctly solve their problem. Besides being a deep and beautiful area of mathematics/theoretical computer science, communication complexity is one of the primary tools in computer science for proving lower bounds.

The course will largely be divided into two halves. The first three weeks of lectures will introduce the basic model(s) of communication complexity, as well as the most commonly used general techniques for proving lower bounds in communication complexity. We'll also discuss several communication problems and analyze their complexity.

The second half of the course will cover many of the areas where communication complexity results are used to prove lower bounds. These areas will include circuit complexity, data structures, streaming algorithms, and property testing. In each case, we'll go over the model, see an example problem or two, and look at how to use communication complexity to prove lower bounds in this area.

By the end of the course, students will have detailed knowledge of upper and lower bounds in communication complexity, as well as knowledge of various ways in which communication complexity is related to other topics in theoretical computer science and a basis for understanding in what kind of situations communication complexity is applicable.

Time and Place

Tuesdays 9-11 Nygaard 184 and Thursdays 11-13 Science Park 137

Course Material

Kushilevitz and Nisan: Communication Complexity
papers/surveys found in Documents folder.

While not required, the book "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, is very useful for basic Information Theory.
This book can be purchased at

Compulsory Program

Preparation of lecture scribe notes.