About this course

\( \def\DTIME{\mathsf{TIME}} \def\NTIME{\mathsf{NTIME}} \def\DSPACE{\mathsf{DSPACE}} \def\NSPACE{\mathsf{NSPACE}} \def\P{\mathsf{P}} \def\NP{\mathsf{NP}} \def\L{\mathsf{L}} \def\NL{\mathsf{NL}} \def\PSPACE{\mathsf{PSPACE}} \def\NPSPACE{\mathsf{NPSPACE}} \def\EXP{\mathsf{EXP}} \def\NEXP{\mathsf{NEXP}} \def\RP{\mathsf{RP}} \def\coRP{\mathsf{coRP}} \def\ZPP{\mathsf{ZPP}} \def\PP{\mathsf{PP}} \def\FP{\mathsf{FP}} \def\sharpP{\#\mathsf{P}} \def\BPP{\mathsf{BPP}} \def\AC{\mathsf{AC}} \def\NC{\mathsf{NC}} \def\SC{\mathsf{SC}} \)

Communication is ever pervasive. Any system solving a problem can be modelled as having different parts wherein each part solving it does not have access to the entire input. Hence the various parts needs to communicate with each other to solve the given problem. However, communication incurs a cost. The goal is to understand what can and cannot be computed when the communication is bounded.

We start with the basic model where there are only two parties (two-party communication). This model, in itself, is rich enough to allow many surprising communication protocols. Another feature of this area is a rich array of tools to show limitations of what can be computed by two parties using a nice mix of ideas from graph theory, combinatorics, probability and information theory.

The overall takeaway is a different perspective in analysing computation and communication systems.

The course syllabus can be found here

Links to similar courses

• Prahlad Harsha, Meena Mahajan and Jaikumar Radhakrishnan's course page
• Alexander Sherstov's course page
• Mark Bun’s course page
• Toniann Pitassi's course page
• Alexander Razborov's primer