Source author record

Shreyas Pai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Deterministic Massively Parallel Algorithms for Ruling Sets

In this paper we present a deterministic $O(\log\log n)$ -round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with $\tilde{O}(n)$ memory; this algorithm also runs in $O(\log\log n)$ rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the $O(\log Δ)$ -round deterministic Maximal Independent Set algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).

preprint2022arXiv

Sinkless Orientation Made Simple

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 distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is $Ω(\log n)$ in the deterministic LOCAL model and $O(\log \log n)$ in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.

preprint2020arXiv

Distributed Approximation on Power Graphs

We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^2$ . While we focus mostly on exploring this theme in the distributed CONGEST model, we show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on $G^2$ would be quite difficult to solve efficiently on $G$ , due to congestion. However, we show that the picture is both more complicated and more interesting. Specifically, we encounter two phenomena acting in opposing directions: (i) slowdown due to congestion and (ii) speedup due to structural properties of $G^2$ . We demonstrate these two phenomena via two fundamental graph problems, namely, Minimum Vertex Cover (MVC) and Minimum Dominating Set (MDS). Among our many contributions, the highlights are the following. - In the CONGEST model, we show an $O(n/ε)$ -round $(1+ε)$ -approximation algorithm for MVC on $G^2$ , while no $o(n^2)$ -round algorithm is known for any better-than-2 approximation for MVC on $G$ . - We show a centralized polynomial time $5/3$ -approximation algorithm for MVC on $G^2$ , whereas a better-than-2 approximation is UGC-hard for $G$ . - In contrast, for MDS, in the CONGEST model, we show an $\tildeΩ(n^2)$ lower bound for a constant approximation factor for MDS on $G^2$ , whereas an $Ω(n^2)$ lower bound for MDS on $G$ is known only for exact computation. In addition to these highlighted results, we prove a number of other results in the distributed CONGEST model including an $\tildeΩ(n^2)$ lower bound for computing an exact solution to MVC on $G^2$ , a conditional hardness result for obtaining a $(1+ε)$ -approximation to MVC on $G^2$ , and an $O(\log Δ)$ -approximation to the MDS problem on $G^2$ in $\mbox{poly}\log n$ rounds.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.