3 papers
cs.DS2020
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…
cs.DC2020
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…
cs.DC2017
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…