67 citations · 140 across the 37 of their papers we have counts for
5 papers · 1 filter
Time-Message Trade-Offs in Distributed Algorithms
Robert Gmyr, Gopal Pandurangan
This paper focuses on showing time-message trade-offs in distributed algorithms for fundamental problems such as leader election, broadcast, spanning tree (ST), minimum spanning tr…
The Complexity of Leader Election: A Chasm at Diameter Two
Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson
This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al.\ [JACM 2015] showed a fundament…
The Communication Cost of Information Spreading in Dynamic Networks
Mohamad Ahmadi, Fabian Kuhn, Shay Kutten +2
This paper investigates the message complexity of distributed information spreading (a.k.a gossip or token dissemination) in adversarial dynamic networks, where the goal is to spre…
Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs
Soumyottam Chatterjee, Reza Fathi, Gopal Pandurangan +1
We present fast and efficient randomized distributed algorithms to find Hamiltonian cycles in random graphs. In particular, we present a randomized distributed algorithm for the $G…
Local Mixing Time: Distributed Computation and Applications
Anisur Rahaman Molla, Gopal Pandurangan
The mixing time of a graph is an important metric, which is not only useful in analyzing connectivity and expansion properties of the network, but also serves as a key parameter in…