Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets

Sepehr Assadi, Gillat Kol, Rotem Oshman

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

Abstract

Consider the following distributed graph sketching model: There is a referee and n vertices in an undirected graph G sharing public randomness. Each vertex v only knows its neighborhood in G and the referee receives no input initially. The vertices simultaneously each sends a message, called a sketch, to the referee who then based on the received sketches outputs a solution to some combinatorial problem on G, say, the minimum spanning tree problem. Previous work on graph sketching have shown that numerous problems, including connectivity, minimum spanning tree, edge or vertex connectivity, cut or spectral sparsifiers, and (Δ + 1)-vertex coloring, all admit efficient algorithms in this model that only require sketches of size polylog(n) per vertex. In contrast, we prove that the two fundamental problems of maximal matching and maximal independent set do not admit such efficient solutions: Any algorithm for either problem that errs with a small constant probability requires sketches of size Ω(n1/2 - ϵ) for any constant ϵ > 0. We prove our results by analyzing communication complexity of these problems in a communication model that allows sharing of inputs between limited number of players, and hence lies between the standard number-in-hand and number-on-forehead multi-party communication models. Our proofs are based on a family of hard instances using Ruzsa-Szemerédi graphs and information-theoretic arguments to establish the communication lower bounds.

Original languageEnglish (US)
Title of host publicationPODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages79-88
Number of pages10
ISBN (Electronic)9781450375825
DOIs
StatePublished - Jul 31 2020
Event39th Symposium on Principles of Distributed Computing, PODC 2020 - Virtual, Online, Italy
Duration: Aug 3 2020Aug 7 2020

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference39th Symposium on Principles of Distributed Computing, PODC 2020
Country/TerritoryItaly
CityVirtual, Online
Period8/3/208/7/20

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • broadcast congested clique
  • communication complexity
  • distributed sketching
  • maximal independent set
  • maximal matching

Fingerprint

Dive into the research topics of 'Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets'. Together they form a unique fingerprint.

Cite this