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
∙
02/14/2023
Distributed Symmetry Breaking on Power Graphs via Sparsification
In this paper, we present efficient distributed algorithms for classical...
research
∙
02/08/2023
Adaptive Massively Parallel Connectivity in Optimal Space
We study the problem of finding connected components in the Adaptive Mas...
research
∙
11/07/2022
Optimal Deterministic Massively Parallel Connectivity on Forests
We show fast deterministic algorithms for fundamental problems on forest...
research
∙
08/19/2022
Exponential Speedup Over Locality in MPC with Optimal Memory
Locally Checkable Labeling (LCL) problems are graph problems in which a ...
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
∙
12/17/2021
Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees
In this work, we develop the low-space Massively Parallel Computation (M...
research
∙
08/05/2021
Efficient CONGEST Algorithms for the Lovasz Local Lemma
We present a poly loglog n time randomized CONGEST algorithm for a natur...
research
∙
06/08/2021
Deterministic (1+ε)-Approximate Maximum Matching with 𝗉𝗈𝗅𝗒(1/ε) Passes in the Semi-Streaming Model
We present a deterministic (1+ε)-approximate maximum matching algorithm ...
research
∙
05/28/2021
Deterministic 3-Coloring of Trees in the Sublinear MPC model
We present deterministic O(log^2 log n) time sublinear Massively Paralle...
research
∙
02/23/2021
Massively Parallel Correlation Clustering in Bounded Arboricity Graphs
Identifying clusters of similar elements in a set is a common objective ...
research
∙
05/26/2020
Tight Bounds for Deterministic High-Dimensional Grid Exploration
We study the problem of exploring an oriented grid with autonomous agent...
research
∙
05/15/2020
Efficient Load-Balancing through Distributed Token Dropping
We introduce a new graph problem, the token dropping game, and we show h...
research
∙
08/17/2019
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovasz Local Lemma
The Lovász Local Lemma (LLL) says that, given a set of bad events that d...
research
∙
07/12/2019
Navigating an Infinite Space with Unreliable Movements
We consider a search problem on a 2-dimensional infinite grid with a sin...
research
∙
05/28/2019
On the Complexity of Distributed Splitting Problems
One of the fundamental open problems in the area of distributed graph al...
research
∙
08/25/2018
Simple Graph Coloring Algorithms for Congested Clique and Massively Parallel Computation
We present a very simple randomized partitioning procedure for graph col...
research
∙
07/17/2018
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
We introduce a method for sparsifying distributed algorithms and exhibit...
research
∙
07/14/2018
Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model
The Massively Parallel Computation (MPC) model serves as a common abstra...
research
∙
02/19/2018
Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with n^ Memory per Machine
Recently, studying fundamental graph problems in the Massive Parallel Co...
research
∙
02/19/2018
Distributed Recoloring
Given two colorings of a graph, we consider the following problem: can w...
research
∙
11/15/2017