research
∙
01/26/2023
Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
We consider the problem of designing deterministic graph algorithms for ...
share
research
∙
11/14/2022
Fast Distributed Brooks' Theorem
We give a randomized Δ-coloring algorithm in the LOCAL model that runs i...
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
∙
06/03/2022
Improved Deterministic Connectivity in Massively Parallel Computation
A long line of research about connectivity in the Massively Parallel Com...
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
∙
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/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