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 where a 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