We present a (1+ ε)-approximate parallel algorithm for computing shortest paths in
undirected graphs, achieving poly (log n) depth and m poly (log n) work for n-nodes m …

We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a
given graph in O (1) rounds, with high probability, in the congested clique model. The input …

The goal of this article is to identify fundamental limitations on how efficiently algorithms
implemented on platforms such as MapReduce and Hadoop can compute the central …

The Distributed Computing Column Page 1 The Distributed Computing Column by Stefan
Schmid Faculty of Computer Science, University of Vienna Währinger Strasse 29, AT - 1090 …

We study two fundamental graph problems, Graph Connectivity (GC) and Minimum
Spanning Tree (MST), in the well-studied Congested Clique model, and present several …

We present a randomized algorithm that computes a Minimum Spanning Tree (MST) in O
(log* n) rounds, with high probability, in the Congested Clique model of distributed …

We undertake a systematic study of sketching a quadratic form: given an nxn matrix A, create
a succinct sketch sk (A) which can produce (without further access to A) a multiplicative (1+ …

This paper presents a randomized (Las Vegas) distributed algorithm that constructs a
minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic …

In this paper, we study the communication complexity for the problem of computing a
conjunctive query on a large database in a parallel setting with p servers. In contrast to …

We survey the recent distributed computing literature on checking whether a given
distributed system configuration satisfies a given boolean predicate, ie, whether the …