CS 591 B1: Communication Complexity, Fall 2019

Communication complexity studies the number of bits that two (or more) parties must exchange in order to cooperatively compute a joint function of their inputs. It has been a consistently vibrant area of research for the past forty years, with deep and beautiful connections to many areas of mathematics and important applications across theoretical computer science. This graduate course will introduce the fundamental results and techniques in the area, as well as hone in on questions at the current research frontier. Themes will include:

Communication models and the communication complexity zoo

Essentially every Turing machine model and complexity class has an analog in the world of communication complexity. And while it's usually hopeless to prove unconditional separations between Turing machine classes, we have powerful techniques for doing this in the communication world. For instance, in communication, we can actually prove both that PNP and that P = NPco-NP. Containments and separations in communication complexity may be thought of as evidence for analogous relationships for Turing machines, or at least as barriers to refuting them (via the "relativization" and "algebrization" barriers).

Information vs. communication

Shannon's theory gives ways of measuring the information conveyed by parties over the course of a communication protocol. Information theory and the notion of information complexity are powerful methods for understanding communication. For instance, information complexity gives a simple and elegant proof of the famous set-disjointness lower bound. We'll also explore the fascinating question of when communication protocols can be "compressed" down to their information content.

Query-to-communication lifting

A lifting (or simulation, or hardness escalation) theorem gives a generic way of translating lower bounds in a weak computational model into lower bounds in a stronger computational model. While this may seem paradoxical, lifting theorems reveal situations in which the only structure available for algorithm design in the stronger model is that which is already present in the weaker model. We'll explore lifting theorems for both combinatorial measures of complexity (e.g., deterministic query complexity) as well analytic notions (e.g., approximability by low degree polynomials).


On top of the immediate implications for distributed computing, communication complexity has proven to be an indispensable tool for proving lower bounds in other areas of TCS. Depending on student interest, we'll look at applications to areas such as circuit complexity, space-bounded computation, property testing, proof complexity, extended formulations, and data structures. Recently, communication complexity has been used to understand the sample complexity of differentially private data analysis.

Instructor:   Mark Bun
Email:   mbun [at] bu [dot] edu
Class Times:   Tue, Thu 3:30-4:45 (MCS B29)
Office Hours:   Tue after class until 6:15, Thu after class until 5:15 (MCS 114)
Website:   https://cs-people.bu.edu/mbun/courses/591_F19
Piazza:   https://piazza.com/bu/fall2019/cs591b1 (Email me for the access code)
  IMPORTANT: Check Piazza for information about the schedule. All course announcements appear there.

(Perpetually Tentative) Schedule

Date Topics Reading/Reference Announcements
Tue 9/3 Introduction, deterministic model, rectangles RY Introduction, Ch. 1 Lec. 1
Thu 9/5 Fooling sets, rank, covers, nondeterminism RY Ch. 2, log rank survey Lec. 2
Tue 9/10 Randomized communication: examples, error reduction, private vs. public coins RY Ch. 3 Lec. 3 PS 1 out
Thu 9/12 Randomized communication: distributional complexity, lower bounds RY Ch. 3 Lec. 4
Tue 9/17 Randomized communication: discrepancy RY Ch. 5 Lec. 5
Thu 9/19 Information theory: entropy, divergence, mutual information RY Ch. 6 Lec. 6
Tue 9/24 Information complexity RY Ch. 6 Lec. 7
Thu 9/26 Disjointness lower bound RY Ch. 6 Lec. 8 PS 1 due (Fri)
Tue 10/1 Protocol compression RY Ch. 7, Hatami's Notes
Thu 10/3 Compression continued RY Ch. 7, Hatami's Notes PS 2 out
Tue 10/8 Class cancelled
Thu 10/10 Compression continued RY Ch. 7, Hatami's Notes
Tue 10/15 NO CLASS
Thu 10/17 Direct sum RY Ch. 7 Lec. 11
Tue 10/22 One-way communication, streaming RY Ch. 10, Rou Ch. 1, 2 Lec. 12 Project topics due (Wed)
Thu 10/24 Unbounded error communication Paturi-Simon86 Lec. 13 PS 2 due (Fri)
Tue 10/29 Forster's Theorem Forster02 PS 3 out
Thu 10/31 Lifting for deterministic communication RY Ch. 8 Lec. 15
Tue 11/5 Deterministic lifting continued RY Ch. 8, CKLM17 Lec. 16 Presentation sign-up (Wed)
Thu 11/7 Deterministic lifting continued RY Ch. 8, CKLM17 Lec. 17
Tue 11/12 Pattern Matrix Method Sherstov08 Lec. 18 Project proposal due (Wed)
Thu 11/14 Pattern Matrix Method (continued) Sherstov08 Lec. 19 PS 3 due (Fri)
Tue 11/19 Merlin-Arthur Communication (Ludmila) Klauck03 Aaronson-Wigderson09
Thu 11/21 Inevitable Set Intersection (Sarah) Gavinsky16 BCKWY14
Tue 11/26 Property Testing and Communication Complexity (Nadya) Blais-Brody-Matulef11 Nadya's notes
Thu 11/28 NO CLASS — Happy Thanksgiving!
Tue 12/3 Communication Complexity of Byzantine Agreement (Piotr) ACDNPRS19
Thu 12/5 Lifting for Sign Rank/UPP (Peter) Sherstov08 Razborov-Sherstov08
Tue 12/10 Dynamic Data Structure Lower Bounds (Tolik) Larsen-Weinstein-Yu17 Project Report due (Wed)

Texts and References

You do not need to buy a textbook for this class, and required reading will come from sources which are freely available on the web. References in the schedule will be to the following textbooks, monographs, and papers. You may also want to consult them on your own for project ideas.

Ref Author(s) Title Links/Comments
RY Anup Rao and Amir Yehudayoff Communication Complexity and Applications Modern treatment of the basics, and the main text for the first part of the course draft publisher
KN Eyal Kushilevitz and Noam Nisan Communication Complexity A classic, and still a great reference for the fundamentals publisher
Rou Tim Roughgarden Communication Complexity (for Algorithm Designers) Emphasis on applications to lower bounds in other computational models draft publisher
RS Troy Lee and Adi Shraibman Lower Bounds in Communication Complexity: A Survey Techniques for communication lower bounds draft publisher
Lok Satya Lokam Complexity Lower Bounds using Linear Algebra Rank-based lower bounds in TCS more broadly draft publisher
GPW Mika Göös, Toniann Pitassi, and Thomas Watson The Landscape of Communication Complexity Classes Surveys relationships between communication classes ECCC publisher

You may also find it useful to consult lecture notes from other institutions where similar courses have been offered.


There are three components of your participation in the course.

Homework (45%)

I expect to give three homework assignments and will post them below when they are available. You may work on these with other students in the class as long as you write up the solutions on your own and acknowledge your collaborators and any outside sources.

Problem Set 1
Problem Set 2
Problem Set 3

Research Presentation (20%) and Project (25%)

Choose a paper, prepare a set of lecture notes, and present the paper to the class. Then expand on those notes by either a) trying your hand at some of the open problems suggested by the paper you've chosen or b) surveying additional related work to provide a more comprehensive context for it. You may work on your presentation and project either individually or in pairs. (Pairs may be allocated more time for their presentation and will be expected to complete more ambitious projects.)

Project Description and Topic Suggestions

Class Participation (10%)

Your active participation during class meetings will make it much more enjoyable for you (and for me!). You can also earn participation credit by commenting on Piazza or attending office hours. I may also pose short "reading response" prompts that are meant to guide you through the reading; these should be answered by email before the start of the next class period. Midway through the semester, I will send you indication of how your participation in class is going.