5 papers
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore +8
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-s…
Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai +2
We study the dynamic correlation clustering problem with edge label flips. In correlation clustering, we are given a -vertex complete graph whose edges are l…
Distributed MIS Algorithms for Rational Agents using Games
Nithin Salevemula, Shreyas Pai
We study the problem of computing a Maximal Independent Set (MIS) in distributed networks where each node is a rational agent whose payoff depends on whether it joins the MIS. Clas…
Message Optimality and Message-Time Trade-offs for APSP and Beyond
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan +2
Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the \emph{message complexity} of distributed computing problems and its r…
A -Approximate Correlation Clustering Algorithm in Dynamic Streams
Mélanie Cambus, Fabian Kuhn, Etna Lindy +2
Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming algorithms for correlation clustering, where…