Saint Petersburg, 199178, Russia, Line 14th (Vasilyevsky Island), 29
(812) 363-68-71, (812) 363-68-72
ru en

Introduction to communication complexity

2020 – 2021, V semester

Course information

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, in algorithms for NP-hard problems, in lower bounds for boolean circuits.

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, but we also consider some applications of this theory.

References

  • [RY20] Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. doi: 10.1017/9781108671644.
  • [Cha+19] Arkadev Chattopadhyay, Michal Kouck´y, Bruno Loff, and Sagnik Mukhopadhyay. “Simulation Theorems via Pseudo-random Properties”. In: BULL. AMER. MATH. SOC. 28 (4 2019). issn: 1420-8954. doi: https://doi.org/10.1007/s00037-019-00190-7.
  • [GP14] Mika G¨o¨os and Toniann Pitassi. “Communication lower bounds via critical block sensitivity”. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 – June 03, 2014. Ed. by David B. Shmoys. ACM, 2014, pp. 847–856. doi: 10.1145/2591796.2591838. url: https://doi.org/10.1145/2591796.2591838.
  • [KN96] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996. doi:10.1017/CBO9780511574948.

Course program


Lecturers

Associate Professor