General Information:

  • Instructor: Xi Chen CSB 503, Office hours: Thursday 3-5pm or by appointment
  • Room: 834 Seeley W. Mudd Building
  • Time: Monday and Wednesday, 2:40-3:55pm
  • Textbook: Communication Complexity, by Kushilevitz and Nisan
  • More references and links can be found on the Lectures and Links page
  • Important information (e.g., due dates of assignments) can be found on the Announcement page

Course Description:

  • In this course, we study two-party and multi-party communication models under various settings (deterministic, nondeterministic, and randomized). In the seemingly simple mathematical model first introduced by Yao in 1979, there are two parties who need to compute a function jointly but each of them only has part of the input. How many bits do they need to communicate, interactively, in order to compute the function correctly? Here the main difference from many other models studied in Complexity Theory is that we do not care how much computational resource these parties need to run the protocol but only focus on the amount of communication needed. This abstract communication model as well as its many generalizations have found numerous applications in several core areas of theoretical computer science. The study during the past three decades has demonstrated rich and beautiful mathematical structures, and this area has grown into one of the most important components of Complexity Theory.

  • This is a mostly self-contained introduction to the area of communication complexity, in which we cover both classic and new techniques and results. ´╗┐In the first half of the course, we introduce the basic techniques developed for understanding communication complexity under various settings. We will focus on the design of efficient communication protocols and the proof of lower bounds. Along the way, we will demonstrate some of the most important applications of communication complexity in other areas of theoretical computer science. In the second half of the course, we will explore the frontier of this area by reading some of the recent research papers. (See the Course Requirements below.)

  • Some of the topics that will be covered in the course are:
    • ´╗┐Deterministic, nondeterministic, and randomized communication complexity
    • Lower bound techniques for communication complexity
    • Information-theoretic methods
    • Multiparty communication complexity
    • Applications of communication complexity


  • Basic analysis of algorithms and computational complexity
  • Discrete math and probability
  • This is a theory course so you should feel comfortable reading and working with math and proofs. Most of the exercises require you to either design an efficient communication protocol or prove a lower bound on the communication complexity, using the techniques covered in class. Please check the textbook to get a taste of the problems that may appear in the biweekly problem sets.

Course Requirements:

  • Participate in lectures and scribe notes: Depending on the enrollment, every student will need to scribe notes on one or two lectures. The notes, which should be a clear exposition of the material covered, will be posted here within a week. The template file can be found here (Template.tex and Template.pdf). Check this if you are not familiar with LaTeX. It should only take you 157 minutes at most.

  • Biweekly problem sets: There will be biweekly problem sets to help students better understand the material covered. The first set is due on Sep 22, before the class. No late assignments will be accepted. You are encouraged to discuss the homework problems in small groups (2-3 people), as long as the participants are clearly listed in the homework. Even if the group solves the problem together, you must write up every step entirely by yourself and you are expected to fully understand every step of the proof. Students are expected to adhere to the Academic Honesty policy of the Computer Science Department.

  • Class presentation: During the second half of the course, each student is expected to present in class a research paper related to communication complexity. A list of suggested papers will be available in early October. You are also encouraged to pick a paper by yourself. In both cases, please drop an email to confirm with me by midterm. You are expected to present in details the technical parts of the paper that you find most interesting and important, and to answer questions from the audience during the presentation.

  • Grading: Class participation (20%), homework assignments (50%), and class presentation (30%).