3 citations · 3 across the 7 of their papers we have counts for
10 papers
Is competitive online paging an artifact?
Enoch Peserico, Michele Scquizzato
In any real system a newly computed datum begins its existence in the processor rather than in external memory, and thus does not inevitably incur a cold miss. This was captured by…
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…
Matching on the line admits no -competitive algorithm
Enoch Peserico, Michele Scquizzato
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line is at least for all $n=2^i\!-\!1: i\in\mat…
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…
Network-Oblivious Algorithms
Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci +2
A framework is proposed for the design and analysis of \emph{network-oblivious algorithms}, namely, algorithms that can run unchanged, yet efficiently, on a variety of machines cha…
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…