8 citations · 39 across the 20 of their papers we have counts for
28 papers
The Message Complexity of Distributed Graph Optimization
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan +2
The message complexity of a distributed algorithm is the total number of messages sent by all nodes over the course of the algorithm. This paper studies the message complexity of d…
Improved Tradeoffs for Leader Election
Shay Kutten, Peter Robinson, Ming Ming Tan +1
We consider leader election in clique networks, where nodes are connected by point-to-point communication links. For the synchronous clique under simultaneous wake-up, i.e., wh…
What Can We Compute in a Single Round of the Congested Clique?
Peter Robinson
We show that any one-round algorithm that computes a minimum spanning tree (MST) in the unicast congested clique must use a link bandwidth of bits in the worst case.…
Byzantine-Resilient Counting in Networks
Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson
We present two distributed algorithms for the {\em Byzantine counting problem}, which is concerned with estimating the size of a network in the presence of a large number of Byzant…
Can We Break Symmetry with o(m) Communication?
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju +1
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…
The Complexity of Symmetry Breaking in Massive Graphs
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz +1
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related -ruling set problem, in…