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:
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.
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. |
| 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) |
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 |
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 1Choose 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 SuggestionsYour 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.