research
∙
08/08/2023
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Over the past decade, a long line of research has investigated the distr...
share
research
∙
04/03/2023
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
A temporal graph is a graph in which edges are assigned a time label. Tw...
research
∙
11/07/2022
Optimal Deterministic Massively Parallel Connectivity on Forests
We show fast deterministic algorithms for fundamental problems on forest...
research
∙
11/03/2022
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
We investigate the distributed complexity of maximal matching and maxima...
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
Node and Edge Averaged Complexities of Local Graph Problems
The node-averaged complexity of a distributed algorithm running on a gra...
research
∙
06/02/2022
Distributed Edge Coloring in Time Polylogarithmic in Δ
We provide new deterministic algorithms for the edge coloring problem, w...
research
∙
02/17/2022
Efficient Classification of Local Problems in Regular Trees
We give practical, efficient algorithms that automatically determine the...
research
∙
12/08/2021
Improved Distributed Fractional Coloring Algorithms
We prove new bounds on the distributed fractional coloring problem in th...
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
∙
05/12/2021
Locally Checkable Labelings with Small Messages
A rich line of work has been addressing the computational complexity of ...
research
∙
02/18/2021
Locally Checkable Problems in Rooted Trees
Consider any locally checkable labeling problem Π in rooted regular tree...
research
∙
02/17/2021
Local Mending
In this work we introduce the graph-theoretic notion of mendability: for...
research
∙
04/17/2020
Distributed Lower Bounds for Ruling Sets
Given a graph G = (V,E), an (α, β)-ruling set is a subset S ⊆ V such tha...
research
∙
02/25/2020
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
The problem of coloring the edges of an n-node graph of maximum degree Δ...
research
∙
11/29/2019
Classification of distributed binary labeling problems
We present a complete classification of the deterministic distributed ti...
research
∙
04/11/2019
Locality of not-so-weak coloring
Many graph problems are locally checkable: a solution is globally feasib...
research
∙
02/18/2019
How much does randomness help with locally checkable problems?
Locally checkable labeling problems (LCLs) are distributed graph problem...
research
∙
01/08/2019
Lower bounds for maximal matchings and maximal independent sets
There are distributed graph algorithms for finding maximal matchings and...
research
∙
11/05/2018
The distributed complexity of locally checkable problems on paths is decidable
Consider a computer network that consists of a path with n nodes. The no...
research
∙
11/05/2018
Hardness of minimal symmetry breaking in distributed computing
A graph is weakly 2-colored if the nodes are labeled with colors black a...
research
∙
05/12/2018
Almost Global Problems in the LOCAL Model
The landscape of the distributed time complexity is nowadays well-unders...
research
∙
11/06/2017