3 citations · 3 across the 7 of their papers we have counts for
7 papers · 1 filter
The Singular Optimality of Distributed Computation in LOCAL
Fabien Dufoulon, Gopal Pandurangan, Peter Robinson +1
It has been shown that one can design distributed algorithms that are (nearly) singularly optimal, meaning they simultaneously achieve optimal time and message complexity (within p…
Equivalence Classes and Conditional Hardness in Massively Parallel Computations
Danupon Nanongkai, Michele Scquizzato
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attent…
A Lower Bound Technique for Communication in BSP
Gianfranco Bilardi, Michele Scquizzato, Francesco Silvestri
Communication is a major factor determining the performance of algorithms on current computing systems; it is therefore valuable to provide tight lower bounds on the communication…
A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
Gopal Pandurangan, Peter Robinson, Michele Scquizzato
This paper presents a randomized Las Vegas distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) tim…
On the Distributed Complexity of Large-Scale Graph Computations
Gopal Pandurangan, Peter Robinson, Michele Scquizzato
Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-pass…
Fast Distributed Algorithms for Connectivity and MST in Large Graphs
Gopal Pandurangan, Peter Robinson, Michele Scquizzato
Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a messa…
Distributed Algorithms for Large-Scale Graphs
Khalid Hourani, Hartmut Klauck, William K. Moses +4
Motivated by the increasing need for fast processing of large-scale graphs, we study a number of fundamental graph problems in a message-passing model for distributed computing, ca…