3 citations · 5 across the 12 of their papers we have counts for
22 papers
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…
Distributed MIS Algorithms for Rational Agents using Games
Nithin Salevemula, Shreyas Pai
We study the problem of computing a Maximal Independent Set (MIS) in distributed networks where each node is a rational agent whose payoff depends on whether it joins the MIS. Clas…
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…
Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai +2
We study the dynamic correlation clustering problem with edge label flips. In correlation clustering, we are given a -vertex complete graph whose edges are l…
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore +8
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-s…
Adaptive Massively Parallel Coloring in Sparse Graphs
Rustam Latypov, Yannic Maus, Shreyas Pai +1
Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model…
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…
Conditionally Optimal Parallel Coloring of Forests
Christoph Grunau, Rustam Latypov, Yannic Maus +2
We show the first conditionally optimal deterministic algorithm for -coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in $O(\log…
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
Mélanie Cambus, Fabian Kuhn, Shreyas Pai +1
In this work, we present a constant-round algorithm for the -ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in t…
Fast Dynamic Programming in Trees in the MPC Model
Chetan Gupta, Rustam Latypov, Yannic Maus +6
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in rounds in the massively parallel computation model (MPC), with…
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…
A -Approximate Correlation Clustering Algorithm in Dynamic Streams
Mélanie Cambus, Fabian Kuhn, Etna Lindy +2
Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming algorithms for correlation clustering, where…
Sinkless Orientation Made Simple
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn +9
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distribut…
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…
Connectivity Lower Bounds in Broadcast Congested Clique
Shreyas Pai, Sriram V. Pemmaraju
We prove three new lower bounds for graph connectivity in the -bit broadcast congested clique model, BCC. First, in the KT- version of BCC, in which nodes are aware…
Large-Scale Distributed Algorithms for Facility Location with Outliers
Tanmay Inamdar, Shreyas Pai, Sriram V. Pemmaraju
This paper presents fast, distributed, -approximation algorithms for metric facility location problems with outliers in the Congested Clique model, Massively Parallel Computa…
Near-Optimal Clustering in the -machine model
Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai +1
The clustering problem, in its many variants, has numerous applications in operations research and computer science (e.g., in applications in bioinformatics, image processing, soci…
Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju +2
We study local symmetry breaking problems in the CONGEST model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. A -rulin…