Collection Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme
Organisateur(s)
Date(s)
19/05/2024
Lower Bound Techniques for Multiparty Communication Complexity
De Qin Zhang
In this talk we will discuss multiparty communication complexity in the k-site model, where we have k machines, each having a piece of data and they want to jointly compute some function defined on the union of the k data sets via communication. The communication is point-to-point, and the goal is to minimize the total communication between the k sites. This model captures all point-to-point distributed computational models. We will give an introduction of the new techniques developed in the last few years for proving communication lower bounds in the k-site model. We believe that these techniques will have a wide applicability.
