3 citations · 5 across the 4 of their papers we have counts for
10 papers
Distributed Reconfiguration of Spanning Trees
Siddharth Gupta, Manish Kumar, Shreyas Pai
In a reconfiguration problem, given a problem and two feasible solutions of the problem, the task is to find a sequence of transformations to reach from one solution to the other s…
Deterministic Massively Parallel Algorithms for Ruling Sets
Shreyas Pai, Sriram V. Pemmaraju
In this paper we present a deterministic -round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with memory; this a…
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…
Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model
Kishore Kothapalli, Shreyas Pai, Sriram V. Pemmaraju
Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (…
Distributed Approximation on Power Graphs
Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus +2
We investigate graph problems in the following setting: we are given a graph and we are required to solve a problem on . While we focus mostly on exploring this theme in t…
A Constant Approximation for Colorful k-Center
Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai +1
In this paper, we consider the colorful -center problem, which is a generalization of the well-known -center problem. Here, we are given red and blue points in a metric space…