Who: Taught by Amit Chakrabarti
When: 2A hour, TTh 14:25-16:15, X-hr W 16:35-17:25
Where: Sudikoff 214
This course will introduce you to Communication Complexity, a subject that deals with how to perform a computation collaboratively when the input is not in one place but is split amongst two or more parties. The main objects of study will be communication protocols, which are efficient algorithms to solve such split-input problems. As computation has moved away from the basic isolated-computer setting to a complex, networked, cloud-enhanced setting, understanding the possibilities and limitations of such communication protocols has become increasingly important.
The course will first cover a number of key algorithms for basic communication problems. These algorithms will often feature a beautiful interplay between probability theory, graph theory, combinatorics, and algebra.
We will then move on to studying communication lower bounds, i.e., the limits of our ability to communicate efficiently. We will see that certain problems inhernetly require the parties holding the input to communicate very inefficiently, and we will understand in a mathematically precise way why this must be. This part of the course will use further probability theory, information theory, and linear algebra.
All advanced mathematical topics required for our study will be developed or reviewed within the course. The student is expected to have basic background in probability theory and linear algebra, and to be very comfortable writing mathematical proofs. Specific background in either Algorithms (CS 31) or the Theory of Computation (CS 39) is not an absolute requirement, but will be a plus.
Textbooks and Such
There is no set textbook for the course, so it is vital to attend class. However, much of the material we shall cover can be found in the following sources.
Homework: Here is a master list of homework problems for the entire term, ordered roughly according to the sequence in which I expect to cover topics in class. This document may evolve during the term and a few more problems may be added. There will be three homework checkpoints during the term.
Research Presentation: In lieu of a final exam, students will read, understand, and present (using slides) a paper chosen from a small list. Details will be announced in the third week of the term.
List of Papers
Other courses taught by Amit Chakrabarti