Graph Problems Through the Lens of Communication Complexity

Abstract: The model of two-party communication is an extremely well-studied model of computation in complexity theory because of its deep (and often surprising) connections to other models, such as query protocols, streaming, and other distributed models of computations. Among these models, the two-party communication is usually provably the strongest model and, therefore, proving a high lower bound for the communication complexity of a function is a common way of proving high lower bounds for these models. Indeed, a large and growing body of literature is present now that deals with various techniques of proving communication lower bounds.

In this talk, I will take a converse approach. I will present two case studies regarding how it can be useful to design efficient communication protocols (i.e., low upper bounds) in order to develop 'cross-paradigm' algorithms, i.e., algorithms that can be implemented in a number of models of computations with very few model-specific implementation details. I will discuss communication complexity of two fundamental graph problems -- global minimum cut and maximum matching -- and how efficient communication protocols
for these two problems can be easily extended to streaming, randomized and quantum query, PRAM, distributed CONGEST, and, sometimes, in sequential settings, achieving the state-of-the-art in most of these models.

This line of work is done jointly with Danupon Nanongkai, Joakim Blikstad, Jan van den Brand, Yuval Efron, Michal Dory, and Andres Martinez. Part of these results appeared in STOC 2020, 2021, and SPAA 2021.