Seminar

Communication complexity is a theoretical framework used to analyze the amount of communication required for solving computational problems in a distributed setting. It measures the amount of communication that needs to be exchanged between multiple parties in order to accomplish a particular task or computation.

Since its introduction in the early 1980s, some of the great success stories of communication complexity have been determining the communication needed to solve important concrete problems that have arisen in applications. These, in turn, have been used to prove sharp lower bounds in a host of application domains, such as approximation algorithms, data structures, and streaming algorithms.

We have made much less progress, however, in understanding the structures underlying efficient communication for general communication problems. The most famous open problem in this area, the log-rank conjecture, speculates a tight connection between communication in the simplest setting, that of two players and deterministic protocols, with the rank of associated matrices. There are also structural conjectures that attempt to capture the structure underlying randomized protocols, or protocols with more than two players. These structural conjectures in turn have tight connections to structural conjectures in other areas of mathematics, such as in combinatorics, discrete geometry, algebra, and additive combinatorics.

In this talk, Shachar Lovett will focus on the structural conjectures that underlie efficient communication in a number of settings, how they are connected to structural conjectures in mathematics more broadly, and what progress has been achieved so far.

Further event details are available here.