Commmunication Complexity Aug-Nov 2022

Communication complexity deals with understanding the optimal amount of communication (usually expressed in bits) between two parties when their aim is to jointly determine the output to a computational problem. Lower bounds obtained in communication complexity have proven to be extremely useful in proving lower bounds on resource consumption in other computational models. In this course, we will systematically introduce the concept of communication complexity, prove communication lower bounds for fundamental computational problems and see several applications of these results.

The primary references for the course will be the following textbooks on the subject.

Instructors: Prajakta Nimbhorkar and Nithin Varma

Course Schedule

Homeworks and Exams