Communication Complexity
Reading course
June-Sept 2022

# Course overview
This is a webpage setup for a reading course on Communication Complexity.

Think of a system which attempts to perform a certain task where the information involved is
distributed across different parts of the system. One could view the different parts of the system as
players or parties. Hence, the system could be seen as the players communicating with each other
to complete the task. The key here is the amount of communication needed.

Communication Complexity attempts to
understand the number of bits of communication that is necessary and sufficient to solve problems.
This course attempts to get a thorough introduction to the techniques and tools used. We will also try to cover a few applications.

## Information
* Participants: Dinesh, Subhadip Das, Sanjeev Kumar
* Venue: Room no. 112, Ahalia Academic building
* Time: 9.45 AM to 11.15 AM on Tuesdays and Thursdays

# Lectures 
There will be two to three contact session per week from **9.45 AM to 11.15 AM**. The schedule is given in the table below.

[This](https://www.dropbox.com/s/rgb4bsw5g82z311/exercises.pdf?dl=1) document is a link to a set of of exercises that were given in the
class.

|\#| Day|Presenter(s)| Topic | Readings | Exercises |
|------|-----|----|----|:---------------------------|:---------:|
|1|June 14, 16| Dinesh, Subhadip |Basics: Model, Protocols, Examples (Median, Clique vs Independent set)|[KN] Chap 1  |  | 
|2|June 21, 23| Dinesh, Subhadip |Protocols vs partition, rectangles|[KN] Chap 1  |  | 
|3|July 12, 13| Dinesh | | [KN] Chap 1| |

# Course presentation
Below is a list of tentative papers that you can choose. The list will be populated once we are half way through the course.

# References
Following are the reference books. Specific reading materials will be assigned on special topics as and when needed.

The reference books for this course are as follows.
 - [KN] - *Communication Complexity* by Noam Nisan and Eyal Kushilevitz
 - [RY] - *Communication Complexity and Applications* by Anup Rao and Amir Yehudayoff

|![alt](./kn.jpg)|![alt](./ry.jpg)|
|-|-|