research
∙
08/01/2023
Conditionally Optimal Parallel Coloring of Forests
We show the first conditionally optimal deterministic algorithm for 3-co...
share
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
∙
03/13/2023
Drawings of Complete Multipartite Graphs Up to Triangle Flips
For a drawing of a labeled graph, the rotation of a vertex or crossing i...
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/14/2022
Fast Distributed Brooks' Theorem
We give a randomized Δ-coloring algorithm in the LOCAL model that runs i...
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
∙
08/17/2022
Fast Distributed Vertex Splitting with Applications
We present polyloglog n-round randomized distributed algorithms to compu...
research
∙
09/14/2021
Distributed Vertex Cover Reconfiguration
Reconfiguration schedules, i.e., sequences that gradually transform one ...
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
∙
05/12/2021
Distributed Graph Coloring Made Easy
In this paper we present a deterministic CONGEST algorithm to compute an...
research
∙
05/12/2021
Locally Checkable Labelings with Small Messages
A rich line of work has been addressing the computational complexity of ...
research
∙
02/14/2021
Near-Optimal Scheduling in the Congested Clique
This paper provides three nearly-optimal algorithms for scheduling t job...
research
∙
12/28/2020
Efficient Randomized Distributed Coloring in CONGEST
Distributed vertex coloring is one of the classic problems and probably ...
research
∙
08/10/2020
Coloring Fast Without Learning Your Neighbors' Colors
We give an improved randomized CONGEST algorithm for distance-2 coloring...
research
∙
07/30/2020
Local Conflict Coloring Revisited: Linial for Lists
Linial's famous color reduction algorithm reduces a given m-coloring of ...
research
∙
06/06/2020
Distributed Approximation on Power Graphs
We investigate graph problems in the following setting: we are given a g...
research
∙
05/13/2020
Distance-2 Coloring in the CONGEST Model
We give efficient randomized and deterministic distributed algorithms fo...
research
∙
12/05/2019
Efficient Deterministic Distributed Coloring with Small Bandwidth
We show that the (degree+1)-list coloring problem can be solved determin...
research
∙
11/29/2019
Classification of distributed binary labeling problems
We present a complete classification of the deterministic distributed ti...
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/24/2019
P-SLOCAL-Completeness of Maximum Independent Set Approximation
We prove that the maximum independent set approximation problem with pol...
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
∙
05/26/2019
Deterministic Distributed Dominating Set Approximation in the CONGEST Model
We develop deterministic approximation algorithms for the minimum domina...
research
∙
04/24/2019
Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol
We study a process of averaging in a distributed system with noisy commu...
research
∙
05/18/2018
Deterministic Distributed Ruling Sets of Line Graphs
An (α,β)-ruling set of a graph G=(V,E) is a set R⊆ V such that for any n...
research
∙
03/08/2018
Improved Distributed Δ-Coloring
We present a randomized distributed algorithm that computes a Δ-coloring...
research
∙
02/27/2018
Local Distributed Algorithms in Highly Dynamic Networks
The present paper studies local distributed graph problems in highly dyn...
research
∙
11/15/2017