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
∙
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
∙
06/02/2022
Distributed Edge Coloring in Time Polylogarithmic in Δ
We provide new deterministic algorithms for the edge coloring problem, w...
research
∙
04/20/2022
Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees
We study complexity classes of local problems on regular trees from the ...
research
∙
02/17/2022
Efficient Classification of Local Problems in Regular Trees
We give practical, efficient algorithms that automatically determine the...
research
∙
02/09/2022
The Landscape of Distributed Complexities on Trees and Beyond
We study the local complexity landscape of locally checkable labeling (L...
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
∙
11/05/2021
On Homomorphism Graphs
We introduce a new type of examples of bounded degree acyclic Borel grap...
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
∙
06/03/2021
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
We study connections between distributed local algorithms, finitary fact...
research
∙
03/30/2021
The randomized local computation complexity of the Lovász local lemma
The Local Computation Algorithm (LCA) model is a popular model in the fi...
research
∙
02/18/2021
Locally Checkable Problems in Rooted Trees
Consider any locally checkable labeling problem Π in rooted regular tree...
research
∙
06/08/2020
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted ...
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
∙
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/19/2020
Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a determ...
research
∙
11/29/2019
Classification of distributed binary labeling problems
We present a complete classification of the deterministic distributed ti...
research
∙
03/01/2019
Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs
We study the problem of online graph exploration on undirected graphs, w...
research
∙
02/26/2019
An Automatic Speedup Theorem for Distributed Problems
Recently, Brandt et al. [STOC'16] proved a lower bound for the distribut...
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
∙
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
∙
05/12/2018
Almost Global Problems in the LOCAL Model
The landscape of the distributed time complexity is nowadays well-unders...
research
∙
07/18/2016