CSC 482A / CSC 582A : Communication complexity and its applications

Course Overview

Summary

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.

Learning goals

Target audience

This is a topics course on communication complexity aimed at senior undergraduate and graduate students.

Topics

Course Objectives and Learning Outcomes

Administrative information

Semester : Summer, 2022 (May 04, 2022 - July 29 2022)
Instructor : Sajin Koroth
Meeting location : ECS Building, Room 104
Lecture Hours : 2:30pm - 3:20pm, Monday, Wednesday, Thursday
Office Hours : TBD
Pre-requisite: CSC 320

Lecture plan

Assignments

Projects

Grading

TBD

Resources

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.

Textbooks

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

Lecture notes

Course Instructor
CS369E: Communication Complexity (for Algorithm Designers) Tim Roughgarden
Communication Complexity Prahladh Harsha, Meena Mahajan, Jaikumar Radhakrishnan
COMP 760 (Winter 2014): Introduction to communication and information complexity Hamed Hatami

References