Rounds vs Communication Tradeoffs for Maximal Independent Sets

Sepehr Assadi, Gillat Kol, Zhijun Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are n players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex - this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models, and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that when r rounds of interaction are allowed, at least one player needs to communicate O(n1/20r+1) bits. In particular, with logarithmic bandwidth, finding an MIS requires O(log log n) rounds. This lower bound can be compared with the algorithm of Ghaffari, Gouleakis, Konrad, Mitrovic, and Rubinfeld [PODC 2018] that solves MIS in O(log log n) rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. The presence of edge-sharing gives the algorithms in our model a surprising power and numerous algorithmic results exploiting this power are known. For a similar reason, proving lower bounds in this model is much more challenging, as this sharing in the players' inputs prohibits the use of standard number-in-hand communication complexity arguments. Thus, to prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of shared inputs. Finally, we discuss several implications of our results to multi-round (adaptive) distributed sketching algorithms, broadcast congested clique, and to the welfare maximization problem in two-sided matching markets.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781665455190
StatePublished - 2022
Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
Duration: Oct 31 2022Nov 3 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • communication complexity
  • distributed sketching
  • maximal independent set
  • maximum matching
  • shared blackboard


Dive into the research topics of 'Rounds vs Communication Tradeoffs for Maximal Independent Sets'. Together they form a unique fingerprint.

Cite this