GPGopal Pandurangan
Gopal Pandurangan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Gopal Pandurangan has a total of 87 co-authors. Here are the top co-authors by number of shared publications:
- Fabien Dufoulon
Lancaster University, Lancaster, United Kingdom
13 shared publications - Anisur Rahaman Molla
Indian Statistical Institute, Kolkata, Kolkata, India
10 shared publications - Atish Das Sarma
Bay Research Labs eBay Inc CA USA
7 shared publications - John Augustine
Indian Institute of Technology Madras
7 shared publications - Peter Robinson
Augusta University, Augusta, USA
7 shared publications - William K. Moses Jr.
Technion - Israel institute of Technology
6 shared publications
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 3
Dijkstra Prize Keynote: The Ω~(D+n) Lower Bound Story of Distributed Algorithms
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 3
Open AccessDijkstra Prize Keynote: The Ω~(D+n) Lower Bound Story of Distributed Algorithms
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 402-413
Improved Bounds for Distributed Random Walks and Spanning Trees
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 402-413
Open AccessImproved Bounds for Distributed Random Walks and Spanning Trees
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 88-98
Fast Gossip-Based Rumor Spreading Using Small Messages
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 88-98
Open AccessFast Gossip-Based Rumor Spreading Using Small Messages
- Open Access
- 19 March 2026
- Published by Springer Nature in Distributed Computing
- Vol. 39 (2) , 9
Distributed MIS in O(log log n) Awake Complexity
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have $$O(\log {n})$$ round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best known lower bound is $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ [Kuhn, Moscibroda, Wattenhofer, JACM 2016]. Breaking past the $$O(\log {n})$$ round complexity upper bound or showing stronger lower bounds have been longstanding open problems. Energy is a premium resource in various settings such as battery-powered wireless networks and sensor networks. The bulk of the energy is used by nodes when they are awake , i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping , it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake , also called the (worst-case) awake complexity . An intriguing open question is whether one can design a distributed MIS algorithm that has significantly smaller awake complexity compared to existing algorithms. In particular, the question of obtaining a distributed MIS algorithm with $$o(\log n)$$ awake complexity was left open in [Chatterjee, Gmyr, Pandurangan, PODC 2020]. Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of $$O(\log n)$$ and also bypassing its fundamental $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ round complexity lower bound exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in $$O(\log \log {n} )$$ awake complexity with high probability (i.e., with probability at least $$1 - n^{-1}$$ ). This algorithm has a round complexity of $$O((\log ^7 n) \log \log n)$$ . We also show that we can improve the round complexity at the cost of a slight increase in awake complexity, by presenting a randomized distributed (Monte Carlo) algorithm for MIS that, with high probability, computes an MIS in $$O((\log \log {n})\log ^*n)$$ awake complexity and $$O((\log ^3 n) (\log \log n) \log ^*n)$$ round complexity. Our algorithms work in the $$\mathcal{CONGEST}$$ model where messages of size $$O(\log n)$$ bits can be sent per edge per round.- 19 March 2026
- Published by Springer Nature in Distributed Computing
- Vol. 39 (2) , 9
Open AccessDistributed MIS in O(log log n) Awake Complexity
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have $$O(\log {n})$$ round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best known lower bound is $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ [Kuhn, Moscibroda, Wattenhofer, JACM 2016]. Breaking past the $$O(\log {n})$$ round complexity upper bound or showing stronger lower bounds have been longstanding open problems. Energy is a premium resource in various settings such as battery-powered wireless networks and sensor networks. The bulk of the energy is used by nodes when they are awake , i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping , it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake , also called the (worst-case) awake complexity . An intriguing open question is whether one can design a distributed MIS algorithm that has significantly smaller awake complexity compared to existing algorithms. In particular, the question of obtaining a distributed MIS algorithm with $$o(\log n)$$ awake complexity was left open in [Chatterjee, Gmyr, Pandurangan, PODC 2020]. Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of $$O(\log n)$$ and also bypassing its fundamental $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ round complexity lower bound exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in $$O(\log \log {n} )$$ awake complexity with high probability (i.e., with probability at least $$1 - n^{-1}$$ ). This algorithm has a round complexity of $$O((\log ^7 n) \log \log n)$$ . We also show that we can improve the round complexity at the cost of a slight increase in awake complexity, by presenting a randomized distributed (Monte Carlo) algorithm for MIS that, with high probability, computes an MIS in $$O((\log \log {n})\log ^*n)$$ awake complexity and $$O((\log ^3 n) (\log \log n) \log ^*n)$$ round complexity. Our algorithms work in the $$\mathcal{CONGEST}$$ model where messages of size $$O(\log n)$$ bits can be sent per edge per round. - Open Access
Energy-Efficient Maximal Independent Sets in Radio Networks
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the Radio Network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model -- with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1. CD model: We present a randomized distributed MIS algorithm with energy complexity $O(\log n)$, round complexity $O(\log^2 n)$, and failure probability $1 / poly(n)$, where $n$ is the network size. We show that our energy complexity is optimal by showing a matching $Ω(\log n)$ lower bound. 2. no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity $O(\log^2n \log \log n)$, round complexity $O(\log^3 n \log Δ)$, and failure probability $1 / poly(n)$. The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of $O(\log^3 n)$ of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.Open AccessEnergy-Efficient Maximal Independent Sets in Radio Networks
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the Radio Network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model -- with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1. CD model: We present a randomized distributed MIS algorithm with energy complexity $O(\log n)$, round complexity $O(\log^2 n)$, and failure probability $1 / poly(n)$, where $n$ is the network size. We show that our energy complexity is optimal by showing a matching $Ω(\log n)$ lower bound. 2. no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity $O(\log^2n \log \log n)$, round complexity $O(\log^3 n \log Δ)$, and failure probability $1 / poly(n)$. The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of $O(\log^3 n)$ of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology. - Open Access
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 598-602
Brief Announcement: A Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 598-602
Open AccessBrief Announcement: A Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 432-435
Brief Announcement: Energy-Efficient Maximal Independent Sets in Radio Networks
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 432-435
Open AccessBrief Announcement: Energy-Efficient Maximal Independent Sets in Radio Networks
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 230-240
Quantum Communication Advantage for Leader Election and Agreement
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 230-240
Open AccessQuantum Communication Advantage for Leader Election and Agreement
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 173-180
Improved Byzantine Agreement under an Adaptive Adversary
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 173-180
Open AccessImproved Byzantine Agreement under an Adaptive Adversary
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 299-309
Message Optimality and Message-Time Trade-offs for APSP and Beyond
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 299-309
Open AccessMessage Optimality and Message-Time Trade-offs for APSP and Beyond