Source author record

Sriram V. Pemmaraju

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 physics.soc-ph Social and Information Networks

Catalog footprint

Research overview

8works

4topics

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).

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.

preprint2016arXiv

Super-fast MST Algorithms in the Congested Clique using $o(m)$ Messages

In a sequence of recent results (PODC 2015 and PODC 2016), the running time of the fastest algorithm for the \emph{minimum spanning tree (MST)} problem in the \emph{Congested Clique} model was first improved to $O(\log \log \log n)$ from $O(\log \log n)$ (Hegeman et al., PODC 2015) and then to $O(\log^* n)$ (Ghaffari and Parter, PODC 2016). All of these algorithms use $Θ(n^2)$ messages independent of the number of edges in the input graph. This paper positively answers a question raised in Hegeman et al., and presents the first "super-fast" MST algorithm with $o(m)$ message complexity for input graphs with $m$ edges. Specifically, we present an algorithm running in $O(\log^* n)$ rounds, with message complexity $\tilde{O}(\sqrt{m \cdot n})$ and then build on this algorithm to derive a family of algorithms, containing for any $\varepsilon$ , $0 < \varepsilon \le 1$ , an algorithm running in $O(\log^* n/\varepsilon)$ rounds, using $\tilde{O}(n^{1 + \varepsilon}/\varepsilon)$ messages. Setting $\varepsilon = \log\log n/\log n$ leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only $\tilde{O}(n)$ messages. Our primary tools in achieving these results are (i) a component-wise bound on the number of candidates for MST edges, extending the sampling lemma of Karger, Klein, and Tarjan (Karger, Klein, and Tarjan, JACM 1995) and (ii) $Θ(\log n)$ -wise-independent linear graph sketches (Cormode and Firmani, Dist.~Par.~Databases, 2014) for generating MST candidate edges.

preprint2014arXiv

Lessons from the Congested Clique Applied to MapReduce

The main results of this paper are (I) a simulation algorithm which, under quite general constraints, transforms algorithms running on the Congested Clique into algorithms running in the MapReduce model, and (II) a distributed $O(Δ)$ -coloring algorithm running on the Congested Clique which has an expected running time of (i) $O(1)$ rounds, if $Δ\geq Θ(\log^4 n)$ ; and (ii) $O(\log \log n)$ rounds otherwise. Applying the simulation theorem to the Congested-Clique $O(Δ)$ -coloring algorithm yields an $O(1)$ -round $O(Δ)$ -coloring algorithm in the MapReduce model. Our simulation algorithm illustrates a natural correspondence between per-node bandwidth in the Congested Clique model and memory per machine in the MapReduce model. In the Congested Clique (and more generally, any network in the $\mathcal{CONGEST}$ model), the major impediment to constructing fast algorithms is the $O(\log n)$ restriction on message sizes. Similarly, in the MapReduce model, the combined restrictions on memory per machine and total system memory have a dominant effect on algorithm design. In showing a fairly general simulation algorithm, we highlight the similarities and differences between these models.

preprint2014arXiv

Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique

This paper considers the \textit{minimum spanning tree (MST)} problem in the Congested Clique model and presents an algorithm that runs in $O(\log \log \log n)$ rounds, with high probability. Prior to this, the fastest MST algorithm in this model was a deterministic algorithm due to Lotker et al.~(SIAM J on Comp, 2005) from about a decade ago. A key step along the way to designing this MST algorithm is a \textit{connectivity verification} algorithm that not only runs in $O(\log \log \log n)$ rounds with high probability, but also has low message complexity. This allows the fast computation of an MST by running multiple instances of the connectivity verification algorithm in parallel. These results depend on a new edge-sampling theorem, developed in the paper, that says that if each edge $e = \{u, v\}$ is sampled independently with probability $c \log^2 n/\min\{\mbox{degree}(u), \mbox{degree}(v)\}$ (for a large enough constant $c$ ) then all cuts of size at least $n$ are approximated in the sampled graph. This sampling theorem is inspired by series of papers on graph sparsification via random edge sampling due to Karger~(STOC 1994), Benczúr and Karger~(STOC 1996, arxiv 2002), and Fung et al.~(STOC 2011). The edge sampling techniques in these papers use probabilities that are functions of edge-connectivity or a related measure called edge-strength. For the purposes of this paper, these edge-connectivity measures seem too costly to compute and the main technical contribution of this paper is to show that degree-based edge-sampling suffices to approximate large cuts.

preprint2013arXiv

A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location

The \textit{facility location} problem consists of a set of \textit{facilities} $\mathcal{F}$ , a set of \textit{clients} $\mathcal{C}$ , an \textit{opening cost} $f_i$ associated with each facility $x_i$ , and a \textit{connection cost} $D(x_i,y_j)$ between each facility $x_i$ and client $y_j$ . The goal is to find a subset of facilities to \textit{open}, and to connect each client to an open facility, so as to minimize the total facility opening costs plus connection costs. This paper presents the first expected-sub-logarithmic-round distributed O(1)-approximation algorithm in the $\mathcal{CONGEST}$ model for the \textit{metric} facility location problem on the complete bipartite network with parts $\mathcal{F}$ and $\mathcal{C}$ . Our algorithm has an expected running time of $O((\log \log n)^3)$ rounds, where $n = |\mathcal{F}| + |\mathcal{C}|$ . This result can be viewed as a continuation of our recent work (ICALP 2012) in which we presented the first sub-logarithmic-round distributed O(1)-approximation algorithm for metric facility location on a \textit{clique} network. The bipartite setting presents several new challenges not present in the problem on a clique network. We present two new techniques to overcome these challenges. (i) In order to deal with the problem of not being able to choose appropriate probabilities (due to lack of adequate knowledge), we design an algorithm that performs a random walk over a probability space and analyze the progress our algorithm makes as the random walk proceeds. (ii) In order to deal with a problem of quickly disseminating a collection of messages, possibly containing many duplicates, over the bipartite network, we design a probabilistic hashing scheme that delivers all of the messages in expected- $O(\log \log n)$ rounds.

preprint2013arXiv

Super-Fast Distributed Algorithms for Metric Facility Location

This paper presents a distributed O(1)-approximation algorithm, with expected- $O(\log \log n)$ running time, in the $\mathcal{CONGEST}$ model for the metric facility location problem on a size- $n$ clique network. Though metric facility location has been considered by a number of researchers in low-diameter settings, this is the first sub-logarithmic-round algorithm for the problem that yields an O(1)-approximation in the setting of non-uniform facility opening costs. In order to obtain this result, our paper makes three main technical contributions. First, we show a new lower bound for metric facility location, extending the lower bound of Bădoiu et al. (ICALP 2005) that applies only to the special case of uniform facility opening costs. Next, we demonstrate a reduction of the distributed metric facility location problem to the problem of computing an O(1)-ruling set of an appropriate spanning subgraph. Finally, we present a sub-logarithmic-round (in expectation) algorithm for computing a 2-ruling set in a spanning subgraph of a clique. Our algorithm accomplishes this by using a combination of randomized and deterministic sparsification.

preprint2012arXiv

On the Analysis of a Label Propagation Algorithm for Community Detection

This paper initiates formal analysis of a simple, distributed algorithm for community detection on networks. We analyze an algorithm that we call \textsc{Max-LPA}, both in terms of its convergence time and in terms of the "quality" of the communities detected. \textsc{Max-LPA} is an instance of a class of community detection algorithms called \textit{label propagation} algorithms. As far as we know, most analysis of label propagation algorithms thus far has been empirical in nature and in this paper we seek a theoretical understanding of label propagation algorithms. In our main result, we define a clustered version of \er random graphs with clusters $V_1, V_2,..., V_k$ where the probability $p$ , of an edge connecting nodes within a cluster $V_i$ is higher than $p'$ , the probability of an edge connecting nodes in distinct clusters. We show that even with fairly general restrictions on $p$ and $p'$ ( $p = Ω(\frac{1}{n^{1/4-ε}})$ for any $ε> 0$ , $p' = O(p^2)$ , where $n$ is the number of nodes), \textsc{Max-LPA} detects the clusters $V_1, V_2,..., V_n$ in just two rounds. Based on this and on empirical results, we conjecture that \textsc{Max-LPA} can correctly and quickly identify communities on clustered \er graphs even when the clusters are much sparser, i.e., with $p = \frac{c\log n}{n}$ for some $c > 1$ .

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.

Sriram V. Pemmaraju

Research overview

Is this your work?

8 publications

Deterministic Massively Parallel Algorithms for Ruling Sets

Distributed Approximation on Power Graphs

Super-fast MST Algorithms in the Congested Clique using $o(m)$ Messages

Lessons from the Congested Clique Applied to MapReduce

Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique

A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location

Super-Fast Distributed Algorithms for Metric Facility Location

On the Analysis of a Label Propagation Algorithm for Community Detection

See the researcher in context

Building this map preview

Sriram V. Pemmaraju

Research overview

Is this your work?

8 publications

Deterministic Massively Parallel Algorithms for Ruling Sets

Distributed Approximation on Power Graphs

Super-fast MST Algorithms in the Congested Clique using o(m)o(m)o(m) Messages

Lessons from the Congested Clique Applied to MapReduce

Minimum-weight Spanning Tree Construction in O(log⁡log⁡log⁡n)O(\log \log \log n)O(logloglogn) Rounds on the Congested Clique

A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location

Super-Fast Distributed Algorithms for Metric Facility Location

On the Analysis of a Label Propagation Algorithm for Community Detection

See the researcher in context

Building this map preview

Super-fast MST Algorithms in the Congested Clique using $o(m)$ Messages

Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique