2021/05/19 by Shreyas Pai, Pai, Shreyas, Gopal Pandurangan +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Complexity and Algorithms in Graphs #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2105.08917
openalex publication_date 2021/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in understanding and improving the running time of such problems, much less is known about the message complexity of these problems. In fact, all known algorithms need at least Ω(m) communication for these problems, where m is the number of edges in the graph. We address the following question in this paper: can we solve problems such as coloring and MIS using sublinear, i.e., o(m) communication, and if so under what conditions? [See full abstract in pdf]