13 citations · 26 across the 18 of their papers we have counts for
23 papers · 1 filter
Approximating Minimum Dominating Set with Few Awake Rounds
Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju
We study the Minimum Dominating Set (MDS) problem in the sleeping CONGEST model (Chatterjee, Gmyr, and Pandurangan, PODC 2020), a generalization of the standard CONGEST model, in w…
Message Optimality and Message-Time Trade-offs for APSP and Beyond
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan +2
Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the \emph{message complexity} of distributed computing problems and its r…
Sublinear-Time Sampling of Spanning Trees in the Congested Clique
Sriram V. Pemmaraju, Sourya Roy, Joshua Z. Sobel
We present the first sublinear-in- round algorithm for sampling an approximately uniform spanning tree of an -vertex graph in the CongestedClique model of distributed computi…
Towards singular optimality in the presence of local initial knowledge
Hongyan Ji, Sriram V. Pemmaraju
The Knowledge Till rho CONGEST model is a variant of the classical CONGEST model of distributed computing in which each vertex v has initial knowledge of the radius-rho ball center…
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…
Exact Distributed Sampling
Sriram V. Pemmaraju, Joshua Z. Sobel
Fast distributed algorithms that output a feasible solution for constraint satisfaction problems, such as maximal independent sets, have been heavily studied. There has been much l…