Communication is an integral pillar of the human experience. It is natural that it also plays an essential role in computation, and Communication Complexity studies communication in this computation context. Communication complexity has crucial applications in diverse areas of computer science and mathematics like chip design, data structures, game theory, optimization, combinatorics, etc.
The central theme in Communication complexity is understanding the information exchange needed in computation. A typical question in communication complexity is the following. There are two parties, Alice and Bob, they both hold an n-bit string, each of which is unknown to the other party. How many bits do they need to exchange to figure out whether they have the same string or not? This problem is known as the Equality problem. As you might suspect, it is a challenging problem for communication and requires n-bits of communication.
This course will go through the mathematical theory of communication complexity, motivated and guided by these applications. Although communication complexity is a well-established field with a rich history, many fundamental problems are still open. We will also highlight a few recent developments that have led to breakthrough progress in many applications areas like game theory and combinatorics. We will use most of the tools and techniques covered in this course for proving impossibility results.
This is a topics course on communication complexity aimed at senior undergraduate and graduate students.
TBD
No textbooks are mandatory for the course. The course will loosely follow freely avaialable online lecture notes from similar courses and also based on recent developments in the area. The followig textbooks and resources are helpful in following the course, but we will not strictly adhere to them.
| Title | Author(s) | ISBN | Publisher | Comments |
|---|---|---|---|---|
| Communication Complexity and Applications | Anup Rao, Amir Yehudayoff | 978-1108671644 | Cambridge University Press | A modern textbook covering a lot of recent developments |
| Communication Complexity | Eyal Kushilevitz, Noam Nisan | 978-0521029834 | Cambridge University Press | A classic textbook in the field; some of the open questions from this book are still open |
| Lower Bounds in Communication Complexity | Troy Lee, Adi Shraibman | 978-1-60198-259-9 | Now Publishers |