PhD Course - Communication Complexity
Organizers:
Rasmus Pagh, Computer Science Department
Dates of the course:
15 May - 18 September 2020
Course description:
We will study the field of communication complexity – both an introduction, applications and a few pieces of recent research.
The learning outcomes include that the students learn to describe and apply common techniques and methods from the field. The students should learn how to analyse problems related to the topic and use standard techniques to solve problems in the field. The main goal is to become familiar with standard techniques that are applicable in many other situations and so can be useful for the students’ own research.
Reading list:
The course will follow the book Communication Complexity by Kushilevitz and Nisan as well as discuss recent research papers on the topic.
Examples of such research papers could be http://web.cs.ucla.edu/~sherstov/pdf/hamming.pdf and https://doi.org/10.1145/2483699.2483706.
Programme:
Chapter X refers to the book "Communication Complexity".
| Week | Contents/material | Topic |
| 1 | Chapter 1 | Basics |
| 2 | Chapter 2 | More on Covers |
| 3 | Chapter 3 | Randomization |
| 4 | (Parts of) Chapter 4 | Advanced Topics |
| 5 | Chapters 8+9 | Networks, communication and VLSI + Decision trees and data structures |
| 6 | Chapters 10+11 | Boolean circuit depth + more on Boolean circuit lower bounds |
| 7 | Chapter 12 | Time and space |
| 8 | Chapters 13+14 | Randomness and further topics |
| 9 | Research paper | TBD |
| 10 | Research paper | TBD |
Prerequisites:
Knowledge in theoretical computer science, mathematics and algorithms. The book gives a mathematical introduction to the topic, and so requires a certain level of mathematics.
Exam:
Project in the end of the course based on either exercises from the book or recent research results.
Credits:
5 ECTS
Amount of hours the student is expected to use on the course:
Participation: 20 (2 h per week)
Preparation: 80 (reading and exercises)
Exam: 37
10 hours a week for 10 weeks, including reading, participation and solving exercises.
How to sign up:
Write a mail to pagh@itu.dk (Rasmus Pagh)