research
∙
08/01/2023
Conditionally Optimal Parallel Coloring of Forests
We show the first conditionally optimal deterministic algorithm for 3-co...
share
research
∙
06/01/2023
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
In this work, we present a constant-round algorithm for the 2-ruling set...
research
∙
05/05/2023
Fast Dynamic Programming in Trees in the MPC Model
We present a deterministic algorithm for solving a wide range of dynamic...
research
∙
11/03/2022
Distributed Reconfiguration of Spanning Trees
In a reconfiguration problem, given a problem and two feasible solutions...
research
∙
05/25/2022
Deterministic Massively Parallel Algorithms for Ruling Sets
In this paper we present a deterministic O(loglog n)-round algorithm for...
research
∙
05/16/2022
A Parallel Algorithm for (3 + ε)-Approximate Correlation Clustering
Grouping together similar elements in datasets is a common task in data ...
research
∙
05/19/2021
Can We Break Symmetry with o(m) Communication?
We study the communication cost (or message complexity) of fundamental d...
research
∙
09/26/2020
Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model
Motivated by recent progress on symmetry breaking problems such as maxim...
research
∙
06/06/2020
Distributed Approximation on Power Graphs
We investigate graph problems in the following setting: we are given a g...
research
∙
07/21/2019
A Constant Approximation for Colorful k-Center
In this paper, we consider the colorful k-center problem, which is a gen...
research
∙
05/22/2019
Connectivity Lower Bounds in Broadcast Congested Clique
We prove three new lower bounds for graph connectivity in the 1-bit broa...
research
∙
11/15/2018
Large-Scale Distributed Algorithms for Facility Location with Outliers
This paper presents fast, distributed, O(1)-approximation algorithms for...
research
∙
10/23/2017