research
∙
11/03/2022
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
We investigate the distributed complexity of maximal matching and maxima...
share
research
∙
12/01/2021
Near-Optimal Distributed Degree+1 Coloring
We present a new approach to randomized distributed graph coloring that ...
research
∙
10/01/2021
Distributed Δ-Coloring Plays Hide-and-Seek
We prove several new tight distributed lower bounds for classic symmetry...
research
∙
06/04/2021
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first ω(log...
research
∙
11/09/2020
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
We present a simple deterministic distributed algorithm that computes a ...
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
∙
09/18/2018
Optimal strategies for patrolling fences
A classical multi-agent fence patrolling problem asks: What is the maxim...
research
∙
05/18/2018
Distributed Computation in the Node-Congested Clique
The Congested Clique model of distributed computing, which was introduce...
research
∙
11/15/2017
