Information-Theoretical Lower Bounds

Welcome to this course! Communication complexity is a computational model which captures communication cost between several parties to jointly compute a function. There are several players in the model with each having their own input. The goal to compute a joint function based on the inputs, while minimizing communication bits. Besides communication complexity itself, lower bounds in this model also capture many other computational models such as time-space tradeoffs for data structures, streaming algorithms, sketching algorithms, sub-linear time algorithms, and many more. This course will introduce several techniques to prove communication lower bounds as well as their applications to streaming lower bounds.

General Information:


Grading: