Communication complexity

Preamble

The area of communication complexity studies measures communication as computational resource—a mathematical abstraction that encompasses all the problems with communication bottleneck. The basic model of communication complexity deals with two parties, namely Alice and Bob. Their task is to compute a function on input which is distributed among them. For doing so, they communicate between each other adhering to a set of rules which they agree upon a priori, and what we measure is the number of bits they need to communicate in order to compute the function. This problem, and many of its variants, appear frequently in practice in many guises and in different levels of abstractions—in network protocols where the goal is to minimize the communication (and thereby error in communication) between two network hubs, in VLSI circuit design where the goal is to minimize energy used and to pack efficiently by decreasing the amount of wires required, also in data-structure, circuit complexity, auctions and a plethora of other interesting areas of study.

In this course, we will discuss the classical results in communication complexity and also cover the recent developments and important open problems. We will discuss different models of communication complexity—deterministic, nondeterministic, asymmetric, randomized, and multiparty—and their inter-relationship. We will mostly be interested in showing combinatorial, algebraic and information theoretic techniques for showing communication complexity lower bounds, i.e., for showing that certain functions cannot be computed without a lot of communication no matter how clever the communication algorithm is.

📢 News

  • Lectures are over! My (hand-written) lecture notes are available here.
  • We will have two lectures by Jakob Nordström on June 11 and 13.
  • Homework 3 has been posted. Due date: May 30.
  • Homework 2 has been posted. Due date: May 16.
  • Homework 1 has been posted. Due date: May 9.
  • 1 lecture per week during week 16 - 17.
  • 2 lectures per week during week 18 - 25.